The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
From MaRDI portal
Publication:1185244
DOI10.1016/0022-0000(92)90004-3zbMath0743.68078MaRDI QIDQ1185244
Thomas Lengauer, Klaus W. Wagner
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
The complexity of tree automata and XPath on grammar-compressed trees, Approximating schedules for dynamic process graphs efficiently, Hierarchically specified unit disk graphs, Succinct representation, leaf languages, and projection reductions, The complexity of connectivity problems on context-free graph languages, Bounded MSC communication, Fixpoint logics over hierarchical structures, Unnamed Item
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
