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

Chandra, 1978, Alternation

1981, J. Assoc. Comput. Mach., 28, 114, 10.1145/322234.322243

Dolev, 1981, On Linear Area Embedding of Planar Graphs

Galperin, 1982, Succinct Representations of Graphs

Garey, 1979

Goldschlager, 1977, The monotone and planar circuit value problems are log-space complete for P, SIGACT News, 9, 25, 10.1145/1008354.1008356

Goldschlager, 1982, The maximum flow problem is logspace complete for P, Theoret. Comput. Sci., 21, 105, 10.1016/0304-3975(82)90092-5

Galperin, 1983, Succinct representations of graphs, Inform. Control, 56, 183, 10.1016/S0019-9958(83)80004-7

Immerman, 1979, Length of predicate calculus formulas as a new complexity measure, 337

1981, J. Comput. System Sci., 22, 384, 10.1016/0022-0000(81)90039-8

Karp, 1972, Reducibilities among combinatorial problems, 85

Karp, 1985, Constructing a perfect matching is In 32 random NC, 22

Lengauer, 1982, The complexity of compacting hierarchically specified layouts of integrated circuits, 358

T. Lengauer, Exploiting hierarchy in VLSI design, in “VLSI Algorithms and Architectures” (F. Makedon et al., Eds), Springer Lecture Notes in Computer Science, Vol. 227, pp. 180–193.

Lengauer, 1987, Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs, J. Algorithms, 8, 260, 10.1016/0196-6774(87)90042-3

Lengauer, 1987, Efficient solutions of hierarchical systems of linear equations, Computing, 39, 111, 10.1007/BF02310101

Lengauer, 1988, Efficient solutions of connectivity problems on hierarchically defined graphs, SIAM J. Comput., 17, 1063, 10.1137/0217068

Lengauer, 1988, The efficient analysis of graph properties on languages generated by hyperedge replacement systems, Vol. 317, 379

Lengauer, 1989, Hierarchical planarity testing algorithms, J. Assoc. Comput. Mach., 36, 474, 10.1145/65950.65952

Lengauer, 1990, The binary network flow problem in logspace complete for P, Theoret. Comput. Sci., 75, 357, 10.1016/0304-3975(90)90101-M

Meyer, 1972, The equivalence problem for regular expressions with squaring requires exponential space, 125

Monien, 1981, Time and space bounded complexity classes and bandwidth constrained problems, Vol. 118, 78

Machtey, 1978

C. H. PAPADIMITRIOU AND M. YANNAKAKIS, A note on succinct representation of graphs, Inform. Control, to appear.

Savitch, 1973, Maze recognizing automata and nondeterministic tape complexity, J. Comput. System Sci., 7, 389, 10.1016/S0022-0000(73)80031-5

Stockmeyer, 1973, Word problems requiring exponential time, 1

Sudborough, 1973, On tape-bounded complexity classes and multihead finite automata, 138

Sudborough, 1980, Efficient algorithms for path system problems and application to alternating and time-space complexity classes, 62

Skyum, 1981, A complexity theory based on Boolean algebra, 244

Wagner, 1984, The complexity of problems concerning graphs with regularities, Vol. 176, 544

Wagner, 1986, The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325, 10.1007/BF00289117