Christoph Meinel, Anna Slobodova

Reducibility concepts are fundamental in complexity theory.

Usually, they are defined as follows: A problem P is reducible

to a problem S if P can be computed using a program or device

for S as a subroutine. However, in the case of such restricted

models as ...
more >>>

igor razgon

We introduce a new graph parameter called linear upper maximum induced

matching width \textsc{lu-mim width}, denoted for a graph $G$ by $lu(G)$.

We prove that the smallest size of the \textsc{obdd} for $\varphi$,

the monotone 2-\textsc{cnf} corresponding to $G$, is sandwiched

between $2^{lu(G)}$ and $n^{O(lu(G))}$.

The upper bound ...
more >>>