On the OBDD representation of some graph classes

DOI10.1016/J.DAM.2016.05.028MaRDI QIDQ317396zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Marc Bury

Publication date 30 September 2016

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

Full work available at URL https://doi.org/10.1016/j.dam.2016.05.028

zbMATH Keywords

interval graphsregular graphsordered binary decision diagramsthreshold graphsconvex graphsimplicit graph representations

Mathematics Subject Classification ID

Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Representation of graphs by OBDDs
• OBDD-based representation of interval graphs
• Algorithms and Computation
• SOFSEM 2005: Theory and Practice of Computer Science
• Lower bounds on the OBDD size of two fundamental functions' graphs

Cites work

• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A matrix characterization of interval and proper interval graphs
• Algorithmic graph theory and perfect graphs
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• An optimal time algorithm for minimum linear arrangement of chord graphs
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Branching Programs and Binary Decision Diagrams
• Efficient graph representations
• Enumeration of difference graphs
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Graph Classes: A Survey
• Graph-Based Algorithms for Boolean Function Manipulation
• Implicat Representation of Graphs
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• On a problem of K. Zarankiewicz
• On efficient implicit OBDD-based algorithms for maximal matchings
• On orthogonal ray graphs
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• On the Complexity of Some Ordering Problems
• On the OBDD size for graphs of bounded tree- and clique-width
• On the size of binary decision diagrams representing Boolean functions
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• Priority functions for the approximation of the metric TSP
• Representation of graphs by OBDDs
• Representing graphs implicitly using almost optimal space
• SOFSEM 2004: Theory and Practice of Computer Science
• SOFSEM 2006: Theory and Practice of Computer Science
• Sublinear time algorithms for metric space problems
• Symbolic graphs: Linear solutions to connectivity related problems
• Symbolic topological sorting with OBDDs
• The number of trees
• Threshold graphs and related topics

Cited in

(11)

• OBDD-based representation of interval graphs
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• Representation of graphs by OBDDs
• Algorithms and Computation
• On the OBDD size for graphs of bounded tree- and clique-width
• Representation of graphs and its algorithms based on BDD
• On the OBDD Size for Graphs of Bounded Tree- and Clique-Width
• Ackermann encoding, bisimulations and OBDDs
• Randomized OBDD-based graph algorithms
• Randomized OBDD-based graph algorithms
• String-matching with OBDDs

Describes a project that uses

Uses Software

• Chord

This page was built for publication: On the OBDD representation of some graph classes

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