Till Tantau

The reachability problem for graphs cannot be described, in the

sense of descriptive complexity theory, using a single first-order

formula. This is true both for directed and undirected graphs, both

in the finite and infinite. However, if we restrict ourselves to

graphs in which a certain graph parameter is fixed ...
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 >>>