On the OBDD size for graphs of bounded tree- and clique-width

DOI10.1016/j.disc.2008.01.022zbMath1177.68100OpenAlexW2087617949MaRDI QIDQ1011721

Dieter Rautenbach, Klaus Meer

Publication date: 9 April 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.01.022

zbMATH Keywords

decision diagramclique-widthtree-widthcographordered binary decision diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Randomized OBDD-based graph algorithms ⋮ On the OBDD representation of some graph classes ⋮ Randomized OBDD-Based Graph Algorithms ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ On efficient implicit OBDD-based algorithms for maximal matchings ⋮ Compact representation of graphs of small clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the size of binary decision diagrams representing Boolean functions
• Monadic second-order evaluations on tree-decomposable graphs
• Complement reducible graphs
• BDDs -- design, analysis, complexity, and applications.
• Short encodings of planar graphs and maps
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Succinct representation of general unlabeled graphs
• Symbolic topological sorting with OBDDs
• Easy problems for tree-decomposable graphs
• Graph-Based Algorithms for Boolean Function Manipulation
• Implicat Representation of Graphs
• Branching Programs and Binary Decision Diagrams
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation
• SOFSEM 2004: Theory and Practice of Computer Science
• Representing graphs implicitly using almost optimal space

This page was built for publication: On the OBDD size for graphs of bounded tree- and clique-width