All reports by Author Daniel Král:

__
TR04-051
| 10th June 2004
__

Zdenek Dvorák, Daniel Král, Ondrej Pangrác#### Locally consistent constraint satisfaction problems

__
TR03-061
| 29th August 2003
__

Jan Kára, Daniel Král#### Free Binary Decision Diagrams for Computation of EAR_n

__
TR03-050
| 16th June 2003
__

Daniel Král#### Locally satisfiable formulas

__
TR00-013
| 14th February 2000
__

Daniel Král#### Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Zdenek Dvorák, Daniel Král, Ondrej Pangrác

An instance of a constraint satisfaction problem is $l$-consistent

if any $l$ constraints of it can be simultaneously satisfied.

For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ...
more >>>

Jan Kára, Daniel Král

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined

for n x n Boolean matrices: EAR_n(M)=1 iff the matrix ...
more >>>

Daniel Král

A CNF formula is k-satisfiable if each k clauses of it can be satisfied

simultaneously. Let \pi_k be the largest real number such that for each

k-satisfiable formula with variables x_i, there are probabilities p_i

with the following property: If each variable x_i is chosen randomly and

independently to be ...
more >>>

Daniel Král

Ordered binary decision diagrams (OBDDs) and parity ordered binary

decision diagrams have proved their importance as data structures

representing Boolean functions. In addition to parity OBDDs we study

their generalization which we call parity AOBDDs, give the algebraic

characterization theorem and compare their minimal size to the size

more >>>