{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T21:02:18Z","timestamp":1791061338132,"version":"4.1.0"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,12]]},"abstract":"<jats:p>Using hierarchical definitions we can describe very large graphs in small spaces. In this paper we discuss how such succinct graph descriptions can be used to speed up the solution of graph problems. We present the bottom-up method that solves graph problems without expanding the hierarchical description. This allows solutions that are efficient in terms of the hierarchical graph description instead of the size of the expanded graph. We exemplify the method by giving efficient solutions to connectivity problems on hierarchical graphs. Our results have applications in computer-aided design for integrated circuit design and other engineering problems.<\/jats:p>","DOI":"10.1137\/0217068","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"1063-1080","source":"Crossref","is-referenced-by-count":42,"title":["Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs"],"prefix":"10.1137","volume":"17","author":[{"given":"Thomas","family":"Lengauer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Egon","family":"Wanke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RB0W83","first-page":"127","volume":"1","author":"Bentley J. L.","year":"1983","journal-title":"Adv. in Comput. Res."},{"key":"RCW86","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, S. Winograd,  Matrix multiplication via arithmetic progressions,  Proc. 19th Annual ACM Symposium on Theory of Computing,  1987,  1\u20136","DOI":"10.1145\/28395.28396"},{"key":"RGA82","unstructured":"H. Galperin, Ph.D. Thesis,  Succinct representation of graphs, Department of Electrical Engrg. and Computer Sci., Princeton University, Princeton, NJ,  1982"},{"key":"RGJ79","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"RGW83","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80004-7"},{"key":"RHA69","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"RHS84","unstructured":"M. A. Huang, K. Steiglitz,  A hierarchical compaction algorithm with low page fault complexity,  Proc. MIT-Conference on Advanced Research in VLSI,  1984,  203\u2013212"},{"key":"RKI84","doi-asserted-by":"crossref","unstructured":"C. Kingsley,  A hierarchical error-tolerant compactor,  Proc. 21st Design Automation Conference,  1984,  126\u2013132","DOI":"10.1109\/DAC.1984.1585785"},{"key":"RLE82","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.92"},{"key":"RLM84","unstructured":"T. Lengauer, K. Mehlhorn,  P.  Penfield, Jr.,  The HILL system: A design environment for the hierarchical specification, compaction, and simulation of integrated circuit layouts,  Proc. MIT-Conference on Advanced Research in VLSI, Artech House Company,  1984,  139\u2013149"},{"key":"RLE86A","doi-asserted-by":"crossref","unstructured":"T. Lengauer,  F.  Makedon,  Exploiting hierarchy in VLSI design,  Proc. Aegean Workshop on Computing, Lecture Notes in Computer Science 227, Springer-Verlag, Berlin, New York,  1986,  180\u2013193","DOI":"10.1007\/3-540-16766-8_16"},{"key":"RLE86B","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16761-7_71"},{"key":"RLE87","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90042-3"},{"key":"RLW87","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0039598"},{"key":"RMC80","volume-title":"Introduction to VLSI Systems","author":"Mead C. A.","year":"1980"},{"key":"RSL82","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90086-2"},{"key":"RTA72","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"RUL84","volume-title":"Algorithm aspects of VLSI","author":"Ullman J. D.","year":"1984"},{"key":"RWA84","doi-asserted-by":"crossref","unstructured":"K. Wagner,  The complexity of problems concerning graphs with regularities, Tech. Report, 84\/52, Sektion Mathematik, Universit\u00e4t Jena, German Democratic Republic,  1984","DOI":"10.1007\/BFb0030338"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:33Z","timestamp":1787338113000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["10.1137\/0217068"],"URL":"https:\/\/doi.org\/10.1137\/0217068","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}