On the OBDD representation of some graph classes

DOI10.1016/j.dam.2016.05.028zbMath1346.05193OpenAlexW2464174988MaRDI QIDQ317396

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

ordered binary decision diagrams regular graphs interval graphs threshold graphs convex graphs implicit graph representations

Mathematics Subject Classification ID

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

Uses Software

Chord

Cites Work

Unnamed Item
Unnamed Item
On symbolic OBDD-based algorithms for the minimum spanning tree problem
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
On orthogonal ray graphs
On the size of binary decision diagrams representing Boolean functions
Bipartite permutation graphs with application to the minimum buffer size problem
Representation of graphs by OBDDs
On the OBDD size for graphs of bounded tree- and clique-width
Bipartite permutation graphs
Efficient graph representations
Algorithmic graph theory and perfect graphs
Enumeration of difference graphs
Threshold graphs and related topics
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
An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
The number of trees
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
Graph-Based Algorithms for Boolean Function Manipulation
Implicat Representation of Graphs
Graph Classes: A Survey
Branching Programs and Binary Decision Diagrams
On a problem of K. Zarankiewicz
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

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