Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms

DOI10.1007/11682462_71zbMath1145.68430OpenAlexW1808363799MaRDI QIDQ3525811

Daniel Sawitzki

Publication date: 18 September 2008

Published in: LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11682462_71

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Randomized OBDD-based graph algorithms ⋮ Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations ⋮ Lower bounds on the OBDD size of two fundamental functions' graphs ⋮ On the OBDD representation of some graph classes ⋮ Randomized OBDD-Based Graph Algorithms ⋮ Exponential space complexity for OBDD-based reachability analysis ⋮ New results on the most significant bit of integer multiplication ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ 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 ⋮ Larger lower bounds on the OBDD complexity of integer multiplication ⋮ A note on the size of OBDDs for the graph of integer multiplication

Uses Software

• RelView