On the OBDD representation of some graph classes
DOI10.1016/J.DAM.2016.05.028zbMATH Open1346.05193OpenAlexW2464174988MaRDI QIDQ317396FDOQ317396
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
Recommendations
interval graphsregular graphsordered binary decision diagramsthreshold graphsconvex graphsimplicit graph representations
Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Graph-Based Algorithms for Boolean Function Manipulation
- Graph Classes: A Survey
- Efficient graph representations
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Branching Programs and Binary Decision Diagrams
- Title not available (Why is that?)
- On a problem of K. Zarankiewicz
- Bipartite permutation graphs
- The number of trees
- On orthogonal ray graphs
- An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
- Representation of graphs by OBDDs
- On the OBDD size for graphs of bounded tree- and clique-width
- Enumeration of difference graphs
- Priority functions for the approximation of the metric TSP
- Symbolic topological sorting with OBDDs
- Symbolic graphs: Linear solutions to connectivity related problems
- A matrix characterization of interval and proper interval graphs
- Sublinear time algorithms for metric space problems
- On the Complexity of Some Ordering Problems
- Optimal Distance Labeling for Interval Graphs and Related Graph Families
- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
- Implicat Representation of Graphs
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- Title not available (Why is that?)
- On efficient implicit OBDD-based algorithms for maximal matchings
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- An optimal time algorithm for minimum linear arrangement of chord graphs
- SOFSEM 2006: Theory and Practice of Computer Science
- SOFSEM 2004: Theory and Practice of Computer Science
- Representing graphs implicitly using almost optimal space
- Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
- On the size of binary decision diagrams representing Boolean functions
- Bipartite permutation graphs with application to the minimum buffer size problem
Cited In (8)
- Ackermann encoding, bisimulations and OBDDs
- String-matching with OBDDs
- Representation of graphs and its algorithms based on BDD
- Representation of graphs by OBDDs
- On the OBDD size for graphs of bounded tree- and clique-width
- Algorithms and Computation
- On the OBDD Size for Graphs of Bounded Tree- and Clique-Width
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
Uses Software
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)
