No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
From MaRDI portal
Publication:2946031
DOI10.1007/978-3-319-13524-3_27zbMath1341.68065arXiv1407.0491OpenAlexW1933346394MaRDI QIDQ2946031
Publication date: 15 September 2015
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.0491
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (9)
On the read-once property of branching programs and CNFs of bounded treewidth ⋮ On Compiling Structured CNFs to OBDDs ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ On compiling structured CNFs to OBDDs ⋮ No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth ⋮ Lower bounds on the mim-width of some graph classes ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Parameterized Compilation Lower Bounds for Restricted CNF-Formulas ⋮ Connecting knowledge compilation classes and width parameters
Cites Work
This page was built for publication: No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth