When dealing with special graph classes and algorithmic problems on them, a main source
is the classical book of Golumbic, Algorithmic Graph Theory and Perfect Graphs [454]. The …

Written by prominent experts in the field, this monograph provides the first comprehensive,
unified presentation of the structural, algorithmic and applied aspects of the theory of …

We study the complexity of computing a query on a probabilistic database. We consider
unions of conjunctive queries, UCQ, which are equivalent to positive, existential First Order …

Let f:{0, 1} n→{0, 1} be a monotone Boolean function whose value at any point x∈{0, 1} n
can be determined in time t. Denote by c=⋀ I∈ C⋁ i∈ I xi the irredundant CNF of f, where C …

The goal of Knowledge Compilation is to represent a Boolean expression in a format in
which it can answer a range of online-queries in PTIME. The online-query of main interest to …

A sequence of vertices in a graph G is called a legal dominating sequence if every vertex in
the sequence dominates at least one vertex not dominated by those vertices that precede it …

We give an alternative proof to a characterization theorem of Gurvich for Boolean functions
whose formula size is exactly the number of variables. These functions are called read-once …

This article develops upper and lower bounds for the probability of Boolean functions by
treating multiple occurrences of variables as independent and assigning them new …

Factoring Boolean functions is one of the basic operations in algorithmic logic synthesis.
Current algorithms for factoring Boolean functions are based on some kind of division …

Read-once functions have gained recent, renewed interest in the fields of theory and
algorithms of Boolean functions, computational learning theory and logic design and …