{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:11Z","timestamp":1761611171949},"publisher-location":"Berlin\/Heidelberg","reference-count":38,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354054478X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0017382","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:32:12Z","timestamp":1132644732000},"page":"70-83","source":"Crossref","is-referenced-by-count":9,"title":["An algebraic theory of graph reduction"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Arnborg","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Courcelle","sequence":"additional","affiliation":[]},{"given":"Andrzej","family":"Proskurowski","sequence":"additional","affiliation":[]},{"given":"Detlef","family":"Seese","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, Design and Analysis of Computer Algorithms Addison-Wesley 1972."},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, Efficient Algorithms for Combinatorial Problems on Graphs with Bounded Decomposability \u2014 A Survey, BIT 25 (1985), 2\u201333","journal-title":"BIT"},{"key":"10_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D.G. Corneil and A. Proskurowski, Complexity of Finding Embeddings in a k-tree, SIAM J. Alg. and Discr. Methods 8(1987), 277\u2013287","journal-title":"SIAM J. Alg. and Discr. Methods"},{"key":"10_CR4","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese,An algebraic theory of graph reduction, Technical Report LaBRI TR 90-02, University of Bordeaux (1990)."},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/3-540-19488-6_105","volume":"317","author":"S. Arnborg","year":"1988","unstructured":"S. Arnborg, J. Lagergren and D. Seese, Problems Easy for Tree-decomposable graphs (extended abstract). Proc. 15 th ICALP, Springer Verlag, Lect. Notes in Comp. Sc.317 (1988) 38\u201351","journal-title":"Lect. Notes in Comp. Sc."},{"key":"10_CR6","unstructured":"S. Arnborg, J. Lagergren and D. Seese, Problems Easy for Tree-decomposable graphs to appear, J. of Algorithms."},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski, Characterization and Recognition of Partial 3-trees, SIAM J. Alg. and Discr. Methods 7(1986), 305\u2013314","journal-title":"SIAM J. Alg. and Discr. Methods"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski, Linear Time Algorithms for NP-hard Problems on Graphs Embedded in k-trees, Discr. Appl. Math. 23(1989) 11\u201324","journal-title":"Discr. Appl. Math."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"S. Arnborg, A. Proskurowski and D.G. Corneil, Forbidden minors characterization of partial 3-trees, Discrete Math., to appear","DOI":"10.1016\/0012-365X(90)90292-P"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"M. Bauderon and B. Courcelle, Graph expressions and graph rewritings, Mathematical Systems Theory 20(1987), 83\u2013127","journal-title":"Mathematical Systems Theory"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"J.A. Bern","year":"1987","unstructured":"J.A. Bern, E. Lawler and A. Wong, Linear time computation of optimalsubgraphs of decomposable graphs, J. of Algorithms 8 (1987), 216\u2013235","journal-title":"J. of Algorithms"},{"issue":"4","key":"10_CR12","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1145\/322154.322155","volume":"26","author":"T. Beyer","year":"1979","unstructured":"T. Beyer, W. Jones and S. Mitchell, Linear algorithms for isomorphism of maximal outerplanar graphs, JACM 26(4), Oct.1979, 603\u2013610","journal-title":"JACM"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, Dynamic Programming on Graphs with Bounded Tree-width, MIT\/LCS\/TR-394, MIT 1987.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"10_CR14","unstructured":"H.L. Bodlaender, Improved self-reduction algorithms for graphs with bounded treewidth. RUU-CS-88-29, University of Utrecht 1988."},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(86)90050-2","volume":"42","author":"B. Courcelle","year":"1986","unstructured":"B. Courcelle, Equivalence and transformation of regular systems. Applications to recursive program schemes and grammars, Theoretical Computer Science 42(1986), 1\u201322","journal-title":"Theoretical Computer Science"},{"key":"10_CR16","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 Computation85 (1990) 12\u201375","journal-title":"Information and Computation"},{"key":"10_CR17","unstructured":"B. Courcelle, The monadic second order logic of graphs III: Tree-width, forbidden minors, and complexity issues, Report I-8852, Bordeaux-1 University (1988)"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"B. Courcelle, Graph rewriting: an algebraic and logical approach, in \u201cHandbook of Theoretical Computer Science\u201d, Volume B, J.B. van Leeuwen, Ed. Elsevier, 194\u2013242.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"10_CR19","first-page":"161","volume":"36","author":"B. Courcelle","year":"1988","unstructured":"B. Courcelle, Some applications of logic, universal algebra and of category theory to the theory of graph transformations, Bulletin of the EATCS 36, October 1988, 161\u2013218.","journal-title":"Bulletin of the EATCS"},{"key":"10_CR20","first-page":"30","volume":"344","author":"B. Courcelle","year":"1989","unstructured":"B. Courcelle, The monadic second-order logic of graphs: Definable sets of finite graphs, LNCS 344 (1989) 30\u201353.","journal-title":"LNCS"},{"key":"10_CR21","unstructured":"B. Courcelle, Graphs as relational structures; an algebraic and logical approach, this volume."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North Holland (1976)","DOI":"10.1007\/978-1-349-03521-2"},{"key":"10_CR23","unstructured":"H. Ehrig, M. Nagl, G. Rozenberg and A. Rosenfeld, (Eds.), Proceedings of the 3rd international workshop on Graph Grammars and their Application to Computer Science, Springer Verlag, Lect. Notes in Comp. Sc.291"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"M. Fellows and M. Langston, An analogue of the Myhill-Nerode theorem and its use in computing finite basis characterizations, FOCS 1989 520\u2013525","DOI":"10.1109\/SFCS.1989.63528"},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0201014","volume":"1","author":"M. Hecht","year":"1972","unstructured":"M. Hecht and J. Ullmann, Flow graph reducibility, SIAM J. Comp. 1(1972)188\u2013202","journal-title":"SIAM J. Comp."},{"key":"10_CR26","unstructured":"J. Lagergren, manuscript (1987)"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01788098","volume":"2","author":"Y. Kajitani","year":"1986","unstructured":"Y. Kajitani, A. Ishizuka and S. Ueno, Characterization of partial 3-trees in terms of 3 structures, Graphs and Combinatorics2(1986) 233\u2013246.","journal-title":"Graphs and Combinatorics"},{"key":"10_CR28","first-page":"379","volume":"317","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke, Efficient analysis of graph properties on context-free graph languages, ICALP 88, LNCS 317, (1988), 379\u2013393","journal-title":"ICALP 88, LNCS"},{"key":"10_CR29","unstructured":"J. Matou\u0161ek and R. Thomas, Algorithms finding tree-decompositions of graphs, manuscript (1988)"},{"key":"10_CR30","first-page":"343","volume":"23","author":"N. Robertson","year":"1987","unstructured":"N. Robertson and P.D. Seymour, Some new results on the well-quasi ordering of graphs, Annals of Discrete Mathematics 23(1987), 343\u2013354","journal-title":"Annals of Discrete Mathematics"},{"key":"10_CR31","unstructured":"N. Robertson and P.D. Seymour, Graph Minors X Preprint."},{"key":"10_CR32","unstructured":"N. Robertson and P.D. Seymour, Graph Minors XIII, The Disjoint Path Problem Preprint."},{"key":"10_CR33","unstructured":"N. Robertson and P.D. Seymour, Graph Minors XIV, Wagners conjecture, Preprint."},{"key":"10_CR34","unstructured":"M.M. Syslo, Linear time Algorithm for Coding Outerplanar Graphs, Institute of Computer Science, Wroclaw University, Raport Nr N-20 (1977)"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"J.W. Thatcher, J.B. Wright, Generalized Finite Automata Theory with an Application to a Decision Problem in Second-Order Logic, Mathematical Systems Theory 2(1968), 57\u201381.","journal-title":"Mathematical Systems Theory"},{"key":"10_CR36","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"A. Wald","year":"1983","unstructured":"A. Wald and C.J. Colbourn, Steiner Trees, Partial 2-trees, and Minimum IFI Networks, Networks 13 (1983), 159\u2013167","journal-title":"Networks"},{"key":"10_CR37","unstructured":"T.V. Wimer, Linear algorithms on k-terminal graphs, PhD. thesis, Clemson University, August 1987"},{"key":"10_CR38","unstructured":"T.V.Wimer, S.T.Hedetniemi, and R.Laskar, A methodology for constructing linear graph algorithms, DCS, Clemson University, September 1985."}],"container-title":["Lecture Notes in Computer Science","Graph Grammars and Their Application to Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0017382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T14:38:11Z","timestamp":1683297491000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354054478X"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/bfb0017382","relation":{},"subject":[]}}