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

DOI10.1007/11682462_71MaRDI QIDQ3525811zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Exponential space complexity for OBDD-based reachability analysis
• Symbolic OBDD-based reachability analysis needs exponential space
• SOFSEM 2005: Theory and Practice of Computer Science
• A larger lower bound on the OBDD complexity of the most significant bit of multiplication
• Lower bounds on the OBDD size of two fundamental functions' graphs

Cited in

(18)

• 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
• Priority functions for the approximation of the metric TSP
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• On the OBDD representation of some graph classes
• Symbolic OBDD-based reachability analysis needs exponential space
• Randomized OBDD-based graph algorithms
• Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks
• scientific article; zbMATH DE number 1351076 (Why is no real title available?)
• 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
• Larger lower bounds on the OBDD complexity of integer multiplication
• SOFSEM 2005: Theory and Practice of Computer Science
• Lower bounds on the OBDD size of two fundamental functions' graphs
• A note on the size of OBDDs for the graph of integer multiplication

Describes a project that uses

Uses Software

• RelView

This page was built for publication: Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms

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