Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph parameters:
TR06-035 | 19th January 2006
Till Tantau

The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

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 >>>

TR21-107 | 20th July 2021
igor razgon

Classification of OBDD size for monotone 2-CNFs

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 >>>

ISSN 1433-8092 | Imprint