{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T05:36:17Z","timestamp":1736314577299,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":22,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354017219X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0039598","type":"book-chapter","created":{"date-parts":[[2006,1,31]],"date-time":"2006-01-31T16:55:52Z","timestamp":1138726552000},"page":"100-113","source":"Crossref","is-referenced-by-count":8,"title":["The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems"],"prefix":"10.1007","author":[{"given":"T.","family":"Lengauer","sequence":"first","affiliation":[]},{"given":"K. W.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","first-page":"114","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K.\/Kozen, D.\/Stockmeyer, L.J.: Alternation. Research report RC 7489, IBM Thomas J. Watson Research Center 1979. See also: JACM 28 (1981), 114\u2013133","journal-title":"IBM Thomas J. Watson Research Center 1979"},{"key":"8_CR2","series-title":"Tech. Rep.","first-page":"94305","volume-title":"On linear area embedding of planar graphs","author":"D. Dolev","year":"1981","unstructured":"Dolev, D.\/Trickey, H.: On linear area embedding of planar graphs. Tech. Rep. STAN-CS-81-876, Comp. Sci. Dept., Stanford University, Stanford CA 94305 (1981)"},{"key":"8_CR3","volume-title":"Succinct Representations of Graphs","author":"H. Galperin","year":"1982","unstructured":"Galperin, H.: Succinct Representations of Graphs. Ph.D. Thesis, Dept. of Elec. Eng. and Comp. Sci., Princeton University, Princeton (N.J.) (1982)"},{"key":"8_CR4","volume-title":"Computers & Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R.\/Johnson, D.S.: Computers & Intractability. Freeman, San Francisco (1979)"},{"issue":"2","key":"8_CR5","first-page":"25","volume":"9","author":"L. Goldschlager","year":"1977","unstructured":"Goldschlager, L.: The monotone and planar circuit value problems are log-space complete for P. SIGACT News 9,2 (1977), 25\u201329","journal-title":"The monotone and planar circuit value problems are log-space complete for P. SIGACT News"},{"key":"8_CR6","first-page":"105","volume":"21","author":"L.M. Goldschlager","year":"1982","unstructured":"Goldschlager, L.M.\/Shaw, R.A.\/Staples, J.: The maximum flow problem is log-space complete for P. Theor. Comp. Sci. 21 (1982), 105\u2013111","journal-title":"The maximum flow problem is log-space complete for P. Theor. Comp. Sci."},{"key":"8_CR7","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"Galperin, H.\/Wigderson, A.: Succinct representation of graphs. Information & Control 56 (1983), 183\u2013198","journal-title":"Information & Control"},{"key":"8_CR8","unstructured":"Immerman, N.: Length of predicate calculus formulas as a new complexity measure. 20th IEEE-FOCS (1979), 337\u2013347. See also: JCSS 22 (1981), 384\u2013406"},{"key":"8_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibilities among combinatorial problems. Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibilities among combinatorial problems. Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, eds.), Plenum Press, N.Y. (1972), 85\u2013103"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: The complexity of compacting hierarchically specified layouts of integrated circuits. 23rd IEEE-FOCS (1982), 358\u2013368","DOI":"10.1109\/SFCS.1982.92"},{"key":"8_CR11","series-title":"Theoretische Informatik","volume-title":"Efficient solution of connectivity problems on hierarchically defined graphs","author":"T. Lengauer","year":"1985","unstructured":"Lengauer, T.: Efficient solution of connectivity problems on hierarchically defined graphs. \"Theoretische Informatik\" No. 24, FB 17, Universit\u00e4t-GH Paderborn, Paderborn, West-Germany (1985). Short version in: Proc. of WG '85 (H. Noltemeier, ed.), Trauner Verlag (1985), 201\u2013216"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs. Proc. of STACS 86, Springer Lecture Notes in Computer Science No. 216 (1986), 153\u2013170","DOI":"10.1007\/3-540-16078-7_73"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: Hierarchical planarity testing algorithms. Proc. of ICALP 86, Springer Lecture Notes in Computer Science No. 226 (1986), 215\u2013225","DOI":"10.1007\/3-540-16761-7_71"},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/3-540-16766-8_16","volume":"227","author":"T. Lengauer","year":"1986","unstructured":"Lengauer, T.: Exploiting hierarchy in VLSI design. VLSI Algorithms and Architectures (F. Makedon et al., eds.), Springer Lecture Notes in Computer Science No. 227 (1986), 180\u2013193","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Meyer, A.\/Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE-SWAT (1972), 125\u2013129","DOI":"10.1109\/SWAT.1972.29"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.\/Yannakakis, M.: A note on succinct representation of graphs. Manuscript (1986), to appear in Information & Control.","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"8_CR17","first-page":"389","volume":"7","author":"W.J. Savitch","year":"1973","unstructured":"Savitch, W.J.: Maze recognizing automata and nondeterministic tape complexity. JCSS 7 (1973), 389\u2013403","journal-title":"JCSS"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J.\/Meyer, A.R.: Word problems requiring exponential time. 5th ACM-STOC (1973), 1\u20139","DOI":"10.1145\/800125.804029"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Sudborough, I.H.: On tape-bounded complexity classes and multihead finite automata. 14th IEEE-SWAT (1973), 138\u2013144","DOI":"10.1109\/SWAT.1973.20"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Shyum, S.\/Valiant, L.G.: A complexity theory based on Boolean algebra. Proc. 22nd IEEE-FOCS (1981), 244\u2013253","DOI":"10.1109\/SFCS.1981.3"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Wagner, K.: The complexity of problems concerning graphs with regularities. Proc. of MFCS 84, Springer Lecture Notes in Computer Science No. 176 (1984), 544\u2013552","DOI":"10.1007\/BFb0030338"},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"Wagner, K.: The complexity of combinatorial problems with succinct input representation. Acta Informatica 23 (1986), 325\u2013356","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","STACS 87"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0039598.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T15:28:57Z","timestamp":1736263737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0039598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354017219X"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0039598","relation":{},"subject":[]}}