On compiling structured CNFs to OBDDs

DOI10.1007/978-3-319-20297-6_6MaRDI QIDQ3194709zbMATH OpenOpenAlexFDO

Authors Simone Bova, Friedrich Slivovsky

Publication date 20 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://resolver.obvsg.at/urn:nbn:at:at-ubtuw:3-2794

Mathematics Subject Classification ID

Classical propositional logic (03B05) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On compiling structured CNFs to OBDDs
• The ROBDD size of simple CNF formulas
• On compiling CNFs into structured deterministic DNNFs
• CV-width: a new complexity parameter for CNFs
• Ordered binary decision diagrams, pigeonhole formulas and beyond

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• An 0(n log n) algorithm for the convex bipartite matching problem
• Boolean function complexity. Advances and frontiers.
• Branching Programs and Binary Decision Diagrams
• Chordal bipartite graphs of bounded tree- and clique-width
• CV-width: a new complexity parameter for CNFs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• Improved algorithms for feedback vertex set problems
• Interval graphs: canonical representations in logspace
• Level Schedules for Mixed-Model, Just-in-Time Processes
• Maximum matching in a convex bipartite graph
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• Parametrized complexity theory.
• Recent developments on graphs of bounded clique-width
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Understanding model counting for -acyclic CNF-formulas
• Upper bounds to the clique width of graphs

Cited in

(7)

• Translation among CNFs, characteristic models and ordered binary decision diagrams
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• On compiling structured CNFs to OBDDs
• scientific article; zbMATH DE number 2080994 (Why is no real title available?)
• CV-width: a new complexity parameter for CNFs
• The ROBDD size of simple CNF formulas
• Connecting knowledge compilation classes and width parameters

This page was built for publication: On compiling structured CNFs to OBDDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194709)