The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems

DOI10.1016/0022-0000(92)90004-3zbMath0743.68078OpenAlexW2021380921MaRDI QIDQ1185244

Klaus W. Wagner, Thomas Lengauer

Publication date: 28 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90004-3

zbMATH Keywords

efficient solution of graph problemssuccinct description of large graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The complexity of connectivity problems on context-free graph languages ⋮ Bounded MSC communication ⋮ Languages represented by Boolean formulas ⋮ Compressed Tree Canonization ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ The complexity of tree automata and XPath on grammar-compressed trees ⋮ Unnamed Item ⋮ Approximating schedules for dynamic process graphs efficiently ⋮ Processing succinct matrices and vectors ⋮ The complexity of searching implicit graphs ⋮ Model-checking hierarchical structures ⋮ Fixpoint logics over hierarchical structures ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ Program Repair for Hyperproperties ⋮ The complexity of searching succinctly represented graphs ⋮ Hierarchically specified unit disk graphs ⋮ A Parametrized Analysis of Algorithms on Hierarchical Graphs ⋮ Hierarchically specified unit disk graphs ⋮ A framework for analysing state-abstraction methods ⋮ Succinct representation, leaf languages, and projection reductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The binary network flow problem is logspace complete for P
• Efficient solutions of hierarchical systems of linear equations
• The complexity of combinatorial problems with succinct input representation
• Constructing a perfect matching is in random NC
• Number of quantifiers is better than number of tape cells
• The maximum flow problem is log space complete for P
• On tape-bounded complexity classes and multihead finite automata
• Maze recognizing automata and nondeterministic tape complexity
• Succinct representations of graphs
• Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
• A complexity theory based on Boolean algebra
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Alternation
• Hierarchical planarity testing algorithms
• A note on succinct representations of graphs
• Reducibility among Combinatorial Problems