{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T19:39:22Z","timestamp":1767901162724,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540554882","type":"print"},{"value":"9783540471035","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55488-2_21","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T05:07:40Z","timestamp":1330232860000},"page":"44-69","source":"Crossref","is-referenced-by-count":17,"title":["Processing of hierarchically defined graphs and graph families"],"prefix":"10.1007","author":[{"given":"Franz","family":"H\u00f6fting","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Lengauer","sequence":"additional","affiliation":[]},{"given":"Egon","family":"Wanke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"E. Cohen and N. Megiddo. Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs. In Proceedings of Annual ACM Symposium on Theory of Computing '89, pages 523\u2013534, 1989. Preliminary Version.","DOI":"10.1145\/73007.73057"},{"key":"3_CR2","unstructured":"E. Cohen and N. Megiddo. Recognizing properties of periodic graphs. to appear in: \u201dThe Victor Klee Festschrift\u201d, Honorary Volume of \u201dApplied Geometry and Discrete Mathematics\u201d, 1990."},{"key":"3_CR3","volume-title":"Technical Report 90-110","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Technical Report 90-110, Laboratoire Bordelais de Recherche en Informatique, Universit\u00e9 de Bordeaux I, Talence, France, November 1990."},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"B. Courcelle. An axiomatic definition of context-free rewriting and its application to NLC graph grammars. Theoretical Computer Science, 55:141\u2013181, 1987.","journal-title":"Theoretical Computer Science"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85:12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"3_CR6","first-page":"563","volume-title":"Proceedings of WADS '89, volume 382 of Lecture Notes in Computer Scienece","author":"D. Fernandez-Baca","year":"1989","unstructured":"D. Fernandez-Baca and M.A. Williams. Augmentation problems on hierarchically defined graphs. In F. Dehne, J.R. Sack, and N. Santoro, editors, Proceedings of WADS '89, volume 382 of Lecture Notes in Computer Scienece, pages 563\u2013576. Springer-Verlag, Berlin\/New York, 1989."},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"E. T. Gurari","year":"1984","unstructured":"E.T. Gurari and I.H. Sudborough. Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. Journal of Algorithms, 5:531\u2013546, 1984.","journal-title":"Journal of Algorithms"},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/3-540-50728-0_33","volume-title":"Proceedings of Graph-Theoretical Concepts in Computer Science, WG '88, volume 344 of Lecture Notes in Computer Scienece","author":"A. Habel","year":"1989","unstructured":"A. Habel. Graph-theoretic properties compatible with graph derivations. In J. van Leeuwen, editor, Proceedings of Graph-Theoretical Concepts in Computer Science, WG '88, volume 344 of Lecture Notes in Computer Scienece, pages 11\u201329. Springer-Verlag, Berlin\/New York, 1989."},{"key":"3_CR9","first-page":"15","volume-title":"Proceedings of Graph-Grammars and Their Application to Computer Science '86, volume 291 of Lecture Notes in Computer Scienece","author":"A. Habel","year":"1987","unstructured":"A. Habel and H.J. Kreowski. May we introduce to you: Hyperedge replacement. In H. Ehrig, M. Nagl, A. Rosenfeld, and G. Rozenberg, editors, Proceedings of Graph-Grammars and Their Application to Computer Science '86, volume 291 of Lecture Notes in Computer Scienece, pages 15\u201326. Springer-Verlag, Berlin\/New York, 1987."},{"key":"3_CR10","first-page":"275","volume-title":"Proceedings of TAPSOFT '89, volume 351 of Lecture Notes in Computer Scienece","author":"A. Habel","year":"1989","unstructured":"A. Habel, H.J. Kreowski, and W. Vogler. Decidable boundedness problems for hyperedge-replacement graph grammars. In Proceedings of TAPSOFT '89, volume 351 of Lecture Notes in Computer Scienece, pages 275\u2013289. Springer-Verlag, Berlin\/New York, 1989."},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"K. Iwano and K. Steiglitz. Testing for cycles in infinite graphs with periodic structure. In Proceedings of Annual ACM Symposium on Theory of Computing '87, pages 46\u201355, 1987.","DOI":"10.1145\/28395.28401"},{"key":"3_CR12","volume-title":"Diplomarbeit","author":"B. Kalbers","year":"1991","unstructured":"B. Kalbers. Parameterisierte zellulare Graphgrammatiken. Diplomarbeit, Universit\u00e4t-Gesamthochschule-Paderborn, Paderborn, FRG, Oktober 1991."},{"issue":"3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/321406.321418","volume":"14","author":"R. M. Karp","year":"1967","unstructured":"R.M. Karp, R.E. Miller, and A. Winograd. The organization of computations for uniform recurrence equations. Journal of the ACM, 14(3):563\u2013590, July 1967.","journal-title":"Journal of the ACM"},{"key":"3_CR14","unstructured":"M. Kodialam and J.B. Orlin. Recognizing strong connectivity in (dynamic) periodic graphs and its relation to integer programming. Proceedings of the second annual ACM-SIAM Symposium on Discrete Algorithms, pages 131\u2013135, 1991."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju and G.F. Sullivan. Detecting cycles in dynamic graphs in polynomial time. In Proceedings of Annual ACM Symposium on Theory of Computing '88, pages 398\u2013406, 1988. Preliminary Version.","DOI":"10.1145\/62212.62251"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"T. Lengauer. The complexity of hierarchically specified layouts of integrated circuits. In Ann. ACM Symp. on Foundations of Computer Science, pages 358\u2013368. IEEE, 1982.","DOI":"10.1109\/SFCS.1982.92"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0196-6774(87)90042-3","volume":"8","author":"T. Lengauer","year":"1987","unstructured":"T. Lengauer. Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs. Journal of Algorithms, 8:260\u2013284, 1987.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"3_CR18","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T. Lengauer","year":"1989","unstructured":"T. Lengauer. Hierarchical planarity testing algorithms. Journal of the ACM, 36(3):474\u2013509, 1989.","journal-title":"Journal of the ACM"},{"key":"3_CR19","first-page":"100","volume-title":"Proceedings of STACS '87, volume 247 of Lecture Notes in Computer Scienece","author":"T. Lengauer","year":"1987","unstructured":"T. Lengauer and K. Wagner. The correlation between the complexities of the non-hierarchical and hierarchical version of graph problems. In F. J. Brandenburg, G. Vidal-Naquet, and M. Wirsing, editors, Proceedings of STACS '87, volume 247 of Lecture Notes in Computer Scienece, pages 100\u2013113. Springer-Verlag, Berlin\/New York, 1987. To appear in JCSS."},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02310101","volume":"39","author":"T. Lengauer","year":"1987","unstructured":"T. Lengauer and C. Wieners. Efficient solutions of hierarchical systems of linear equations. Computing, 39:111\u2013132, 1987.","journal-title":"Computing"},{"key":"3_CR21","first-page":"379","volume-title":"Proceedings of International Colloquium on Automata, Languages and Programming, Volume 317 of Lecture Notes in Computer Scienece","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke. Efficient analysis of graph properties on context-free graph languages. In T. Lepist\u00f6 and A. Salomaa, editors, Proceedings of International Colloquium on Automata, Languages and Programming, Volume 317 of Lecture Notes in Computer Scienece, pages 379\u2013393. Springer-Verlag, Berlin\/New York, 1988. To appear in Journal of the ACM."},{"issue":"6","key":"3_CR22","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke. Efficient solution of connectivity problems on hierarchically defined graphs. SIAM Journal of Computing, 17(6):1063\u20131080, December 1988.","journal-title":"SIAM Journal of Computing"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"J.B. Orlin. The complexity of dynamic languages and dynamic optimization problems. In Proceedings of Annual ACM Symposium on Theory of Computing '81, pages 273\u2013293, 1981.","DOI":"10.1145\/800076.802475"},{"key":"3_CR24","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/B978-0-12-566780-7.50022-2","volume-title":"Progress in Combinatorial Optimization","author":"J. B. Orlin","year":"1984","unstructured":"J.B. Orlin. Some problems on dynamic\/periodic graphs. In W.R. Pulleyblank, editor, Progress in Combinatorial Optimization, pages 273\u2013293. Academic Press, Orlando, Florida, 1984."},{"key":"3_CR25","unstructured":"R.J. Parikh. Language generating devices. Technical Report 60, M.I.T. Res. Lab. Electron. Quart. Prog., 1962."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C. Papadimitriou","year":"1986","unstructured":"C. Papadimitriou and M. Yannakakis. A note on succinct representation of graphs. Information and Control, 71:181\u2013185, 1986.","journal-title":"Information and Control"},{"key":"3_CR27","volume-title":"Technical Report 1203","author":"P. Quinton","year":"1990","unstructured":"P. Quinton and Y. Saouter. Computability of recurrence equations. Technical Report 1203, Institute Nationale de Recherche en Informatique et en Automatique, Domaine de Voluceau, Rocquencourt B.P.105, 78153 Le Chesn\u00e1y Cedex, France, 1990."},{"key":"3_CR28","unstructured":"S.K. Rao. Regular iterative algorithms and their implementations on processor arrays. PhD thesis, Stanford University, 1985."},{"issue":"1\u20133","key":"3_CR29","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","volume":"69","author":"G. Rozenberg","year":"1986","unstructured":"G. Rozenberg and E. Welzl. Boundary NLC graph grammars\u2014basic definitions, normal forms, and complexity. Information and Control, 69(1\u20133):136\u2013167, April\/May\/June 1986.","journal-title":"Information and Control"},{"key":"3_CR30","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1137\/0601042","volume":"1","author":"J. B. Saxe","year":"1980","unstructured":"J.B. Saxe. Dynamic programming algorithms for recognizing small bandwidth graphs in polynomial time. SIAM Journal of Algebraic and Discrete Methods, 1:363\u2013369, 1980.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"3_CR31","volume-title":"Diplomarbeit","author":"E. Wanke","year":"1986","unstructured":"E. Wanke. Resultate und Implementierungen hierarchischer Graphenalghorithmen. Diplomarbeit, Universit\u00e4t-Gesamthochschule-Paderborn, Paderborn, FRG, Januar 1986."},{"key":"3_CR32","first-page":"401","volume-title":"Proceedings of STACS '88, volume 294 of Lecture Notes in Computer Scienece","author":"E. Wanke","year":"1988","unstructured":"E. Wanke. PLEXUS: A system for implementing hierarchical graph algorithms. In R. Cori and M. Wirsing, editors, Proceedings of STACS '88, volume 294 of Lecture Notes in Computer Scienece, pages 401\u2013402. Springer-Verlag, Berlin\/New York, 1988. System demonstration."},{"key":"3_CR33","volume-title":"PhD thesis","author":"E. Wanke","year":"1989","unstructured":"E. Wanke. Algorithmen und Komplexit\u00e4tsanalyse f\u00fcr die Verarbeitung hierarchisch definierter Graphen und hierarchisch definierter Graphfamilien. PhD thesis, Universit\u00e4t-Gesamthochschule-Paderborn, 4790 Paderborn, FRG, November 1989."},{"issue":"1","key":"3_CR34","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(91)90035-Z","volume":"94","author":"E. Wanke","year":"1989","unstructured":"E. Wanke. Algorithms for graph problems on BNLC structured graphs. Information and Computation, 94(1):93\u2013122, September 1989.","journal-title":"Information and Computation"},{"key":"3_CR35","first-page":"470","volume-title":"Proceedings of Fundamentals of Computation Theory, volume 380 of Lecture Notes in Computer Scienece","author":"E. Wanke","year":"1989","unstructured":"E. Wanke. The complexity of connectivity problems on context-free graph languages. In J. Csirik, J. Demetrovics, and F. G\u00e9cseg, editors, Proceedings of Fundamentals of Computation Theory, volume 380 of Lecture Notes in Computer Scienece, pages 470\u2013479. Springer-Verlag, Berlin\/New York, 1989."},{"key":"3_CR36","first-page":"415","volume-title":"Proceedings of Fundamentals of Computation Theory, number 529 in Lecture Notes in Computer Scienece","author":"E. Wanke","year":"1991","unstructured":"E. Wanke. On the decidability of certain integer subgraph problems on context-free graph languages. In L. Budach, editor, Proceedings of Fundamentals of Computation Theory, number 529 in Lecture Notes in Computer Scienece, pages 415\u2013426. Springer-Verlag, Berlin\/New York, 1991."},{"key":"3_CR37","unstructured":"E. Wanke. The PLEXUS 4.0 library system programmer's guide. Technical report, Universit\u00e4t-Gesamthochschule-Paderborn, 1991."},{"key":"3_CR38","volume-title":"Lecture Notes in Computer Scienece","author":"E. Wanke","year":"1991","unstructured":"E. Wanke. PLEXUS: Tools for analyzing graph grammars. In Proceedings of Graph-Grammars and Their Application to Computer Science '90, Lecture Notes in Computer Scienece. Springer-Verlag, Berlin\/New York, 1991. System demonstration, to appear."},{"issue":"33","key":"3_CR39","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(89)90140-3","volume":"4","author":"E. Wanke","year":"1989","unstructured":"E. Wanke and M. Wiegers. Undecidability of the bandwidth problem on certain linear graph languages. Information Processing Letters, 4(33):193\u2013197, December 1989.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Data structures and efficient algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55488-2_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:31:22Z","timestamp":1619559082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55488-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540554882","9783540471035"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/3-540-55488-2_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}