Exponential space complexity for OBDD-based reachability analysis

DOI10.1016/j.ipl.2010.07.022zbMath1379.68147OpenAlexW2007609688MaRDI QIDQ1675755

Beate Bollig

Publication date: 3 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.07.022

zbMATH Keywords

computational complexityordered binary decision diagramslower boundstransitive closurereachability analysis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items

Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ Priority functions for the approximation of the metric TSP ⋮ On efficient implicit OBDD-based algorithms for maximal matchings ⋮ Implicit computation of maximum bipartite matchings by sublinear functional operations

Cites Work

• Unnamed Item
• Unnamed Item
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Reduction of OBDDs in linear time
• Symbolic topological sorting with OBDDs
• Symbolic graphs: Linear solutions to connectivity related problems
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• SOFSEM 2005: Theory and Practice of Computer Science
• SOFSEM 2004: Theory and Practice of Computer Science