{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T20:51:11Z","timestamp":1674507071962},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,8,1]],"date-time":"1995-08-01T00:00:00Z","timestamp":807235200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,8]]},"DOI":"10.1007\/bf01293664","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T22:06:22Z","timestamp":1111701982000},"page":"123-137","source":"Crossref","is-referenced-by-count":17,"title":["Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs"],"prefix":"10.1007","volume":"14","author":[{"given":"R. B.","family":"Borie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","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,BIT,25 (1985), 2?23.","journal-title":"BIT"},{"key":"CR2","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 ak-tree,SIAM Journal of Algorithms and Discrete Methods,8 (1987), 277?287.","journal-title":"SIAM Journal of Algorithms and Discrete Methods"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs,Journal of Algorithms,12 (1991), 308?340.","journal-title":"Journal of Algorithms"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"S. Arnborg and A. Proskurowski, Problems on graphs with bounded decomposability,Bulletin of the European Association for Theoretical Computer Science,25 (1985).","DOI":"10.1007\/BF01934985"},{"key":"CR5","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 partialk-trees,SIAM Journal of Algorithms and Discrete Methods,7 (1986), 305?314.","journal-title":"SIAM Journal of Algorithms and Discrete Methods"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and S. Proskurowski, Linear time algorithms for NP-hard problems restricted to partialk-trees,Discrete Applied Mathematics,23 (1989), 11?24.","journal-title":"Discrete Applied Mathematics"},{"key":"CR7","doi-asserted-by":"crossref","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?127.","journal-title":"Mathematical Systems Theory"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M. W. Bern","year":"1987","unstructured":"M. W. Bern, E. L. Lawler, and A. L. Wong, Linear time computation of optimal subgraphs of decomposable graphs,Journal of Algorithms,8 (1987), 216?235.","journal-title":"Journal of Algorithms"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, Dynamic Programming on Graphs with Bounded Tree-Width, Ph.D. Thesis, Massachusetts Institute of Technology (1987).","DOI":"10.1007\/3-540-19488-6_110"},{"key":"CR10","unstructured":"H. L. Bodlaender, Some classes of graphs with bounded tree width,Bulletin of European Association of Theoretical Computer Scientists,36 (1988)."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H. L. Bodlaender","year":"1990","unstructured":"H. L. Bodlaender, Polynomial algorithms for chromatic index and graph isomorphism on partialk-trees,Journal of Algorithms,11 (1990), 631?643.","journal-title":"Journal of Algorithms"},{"key":"CR12","unstructured":"R. B. Borie, Recursively Constructed Graph Families: Membership and Linear Algorithms, Ph.D. Thesis, School of Information and Computer Science, Georgia Institute of Technology (1988)."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1137\/0404043","volume":"4","author":"R. B. Borie","year":"1991","unstructured":"R. B. Borie, R. G. Parker, and C. A. Tovey, Deterministic decomposition of recursive graph classes,SIAM Journal of Discrete Mathematics,4 (1991), 481?501.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R. B. Borie","year":"1992","unstructured":"R. B. Borie, R. G. Parker, and C. A. Tovey, Automatic generation of linear time algorithms from predicate calculus descriptions of problems on recursively constructed graph families,Algorithmica,7 (1992), 555?581.","journal-title":"Algorithmica"},{"key":"CR15","doi-asserted-by":"crossref","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,Theoretical Computer Science,42 (1986), 1?22.","journal-title":"Theoretical Computer Science"},{"key":"CR16","volume-title":"Symposium on Mathematical Foundations of Computer Science","author":"B. Courcelle","year":"1989","unstructured":"B. Courcelle, Monadic second-order logic and context-free graph grammars,Symposium on Mathematical Foundations of Computer Science, Springer-Verlag, New York (1989)."},{"key":"CR17","doi-asserted-by":"crossref","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,Information and Computation,85 (1990), 12?75.","journal-title":"Information and Computation"},{"key":"CR18","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Volume B","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle, Graph rewriting: an algebraic and logic approach,Handbook of Theoretical Computer Science, Volume B, Elsevier, Amsterdam (1990), pp. 193?242."},{"key":"CR19","volume-title":"Graph-Theoretic Concepts in Computer Science, 17th International Workshop","author":"B. Courcelle","year":"1991","unstructured":"B. Courcelle and M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs,Graph-Theoretic Concepts in Computer Science, 17th International Workshop, Springer-Verlag, New York (1991)."},{"key":"CR20","unstructured":"E. El-Mallah, Decomposition and Embedding Problems for Restricted Networks, Ph.D. Thesis, University of Waterloo (1987)."},{"key":"CR21","unstructured":"E. El-Mallah and C. Colbourn, Partialk-tree algorithms,Proceedings of the 250th Anniversary Conference on Graph Theory (1988), pp. 105?119."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0012-365X(90)90364-N","volume":"86","author":"D. L. Grinstead","year":"1990","unstructured":"D. L. Grinstead and P. J. Slater, On minimum dominating sets with minimum intersection,Discrete Mathematics,86 (1990), 239?254.","journal-title":"Discrete Mathematics"},{"key":"CR23","first-page":"563","volume":"1","author":"D. L. Grinstead","year":"1991","unstructured":"D. L. Grinstead and P. J. Slater, On the minimum intersection of minimal dominating sets in series-parallel graphs,Graph Theory, Combinatorics, and Applications,1 (1991), 563?584.","journal-title":"Graph Theory, Combinatorics, and Applications"},{"key":"CR24","unstructured":"A. Habel, Hyperedge Replacement Grammars and Languages, Ph.D. Thesis, Bremen University (1989)."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0304-3975(90)90106-R","volume":"89","author":"A. Habel","year":"1991","unstructured":"A. Habel, H. Kreowski, and W. Vogler, Decidable boundness problems for hyperedge replacement graph grammars,Theoretical Computer Science,89 (1991), 33?62.","journal-title":"Theoretical Computer Science"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/B978-0-12-386870-1.50030-7","volume":"14","author":"E. Hare","year":"1987","unstructured":"E. Hare, S. Hedetniemi, R. Laskar, K. Peters, and T. Wimer, Linear-time computability of combinatorial problems on generalized series-parallel graphs,Discrete Algorithms and Complexity,14 (1987), 437?457.","journal-title":"Discrete Algorithms and Complexity"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D. S. Johnson, TheN P-completeness column: an ongoing guide,Journal of Algorithms,6 (1985), 434?451.","journal-title":"Journal of Algorithms"},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"J. Lagergren and S. Arnborg, Finding minimal forbidden minors using a finite congruence,Proceedings of ICAL P (1991), pp. 532?543.","DOI":"10.1007\/3-540-54233-7_161"},{"key":"CR29","unstructured":"P. C. Liu and R. C. Geldmacher, An O(max(m, n)) algorithm for finding a subgraph homeomorphic toK 4,Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (1980), pp. 597?609."},{"key":"CR30","unstructured":"S. Mahajan and J. G. Peters, Algorithms for regular properties in recursive graphs,Proceedings of the 25th Annual Allerton Conference on Communications, Control, and Computing (1987), pp. 14?23."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(91)90020-Y","volume":"12","author":"J. Matousek","year":"1991","unstructured":"J. Matousek and R. Thomas, Algorithms finding tree-decompositions of graphs,Journal of Algorithms,12 (1991), 1?22.","journal-title":"Journal of Algorithms"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matousek","year":"1992","unstructured":"J. Matousek and R. Thomas, On the complexity of finding iso- and other morphisms for partialk-trees,Discrete Mathematics,108 (1992), 343?364.","journal-title":"Discrete Mathematics"},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"G. Miller and J. Reif, Parallel tree contraction and its applications,Proceedings of the 26th Symposium on Foundations of Computer Science (1985), pp. 478?489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"CR34","volume-title":"Ph.D. Thesis","author":"T. Politof","year":"1983","unstructured":"T. Politof, A Characterization and Efficient Reliability Computation of ?-Y Reducible Networks, Ph.D. Thesis, University of California, Berkeley (1983)."},{"key":"CR35","unstructured":"R. L. Rardin, R. G. Parker, and D. K. Wagner, Definitions, Properties, and Algorithms for Detecting Series-Parallel Graphs, Technical Report, Department of Industrial Engineering, Purdue University (1982)."},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"B. A. Reed, Finding approximate separators and computing tree width quickly,Proceedings of the 24th ACM Symposium on Theory of Computing (1992), pp. 221?228.","DOI":"10.1145\/129712.129734"},{"key":"CR37","unstructured":"M. B. Richey, Combinatorial Optimization on Series-Parallel Graphs: Algorithms and Complexity, Ph.D. Thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology (1985)."},{"key":"CR38","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1002\/net.3230160408","volume":"16","author":"M. B. Richey","year":"1986","unstructured":"M. B. Richey and R. G. Parker, On multiple Steiner subgraph problems,Networks,16 (1986), 423?438.","journal-title":"Networks"},{"key":"CR39","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/0377-2217(88)90258-5","volume":"33","author":"M. B. Richey","year":"1988","unstructured":"M. B. Richey and R. G. Parker, Minimum-maximal matching in series-parallel graphs,European Journal of Operations Research,33 (1988), 98?105.","journal-title":"European Journal of Operations Research"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/net.3230150207","volume":"15","author":"M. B. Richey","year":"1985","unstructured":"M. B. Richey, R. G. Parker, and R. L. Rardin, An efficiently solvable case of the minimum weight equivalent subgraph problem,Networks,15 (1985), 217?228.","journal-title":"Networks"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"N. Robertson and P. Seymour, Disjoint paths-a survey,SIAM Journal of Algorithms and Discrete Methods,6 (1985), 300?305.","journal-title":"SIAM Journal of Algorithms and Discrete Methods"},{"key":"CR42","first-page":"153","volume-title":"Graph minors-a survey inSurveys in Combinatorics","author":"N. Robertson","year":"1985","unstructured":"N. Robertson and P. Seymour, Graph minors-a survey inSurveys in Combinatorics, Cambridge University Press, Cambridge (1985), pp. 153?171."},{"key":"CR43","unstructured":"D. P. Sanders, Linear Algorithms for Graphs of Tree-Width at Most Four, Ph.D. Thesis, Georgia Institute of Technology (1993)."},{"key":"CR44","unstructured":"P. Scheffler, Linear-Time Algorithms for NP-Complete Problems Restricted to Partialk-Trees, R-MATH-03\/87, Akademie der Wissenschaften der DDR (1987)."},{"key":"CR45","unstructured":"P. Sheffier and D. Seese, A combinatorial and logical approach to linear-time computability,Proceedings of European Conference on Computer Algebra (1987), pp. 379?380."},{"key":"CR46","first-page":"412","volume-title":"Lecture Notes in Computer Science, Volume 199","author":"D. Seese","year":"1985","unstructured":"D. Seese,Tree-Particle Graphs and the Complexity of Algorithms, Lecture Notes in Computer Science, Volume 199 (1985), Springer-Verlag, Berlin, pp. 412?421."},{"key":"CR47","first-page":"1061","volume":"2","author":"W. J. Selig","year":"1991","unstructured":"W. J. Selig and P. J. Slater, Minimum dominating, optimally independent vertex sets in graphs,Graph Theory, Combinatorics, and Applications,2 (1991), 1061?1073.","journal-title":"Graph Theory, Combinatorics, and Applications"},{"key":"CR48","first-page":"239","volume":"35A","author":"P. J. Slater","year":"1993","unstructured":"P. J. Slater, Maximum matching among minimum dominating sets,Ars Combinatorica,35A (1993), 239?249.","journal-title":"Ars Combinatorica"},{"key":"CR49","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs,Journal of the Association for Computing Machinery,29 (1982), 623?641.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR50","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, E. Lawler, and R. Tarjan, The recognition of series-parallel digraphs,SIAM Journal of Computing,11 (1982), 289?313.","journal-title":"SIAM Journal of Computing"},{"key":"CR51","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"J. A. Wald","year":"1983","unstructured":"J. A. Wald and C. J. Colbourn, Steiner trees, partial 2-trees, and minimum IFI networks,Networks,13 (1983), 159?167.","journal-title":"Networks"},{"key":"CR52","unstructured":"T. V. Wimer, Linear Algorithms onk-Terminal Graphs, Ph.D. Thesis, Report No. URI-030, Clemson University (1987)."},{"key":"CR53","unstructured":"T. V. Wimer and S. T. Hedetniemi,K-terminal recursive families of graphs,Proceedings of the 250th Anniversary Conference on Graph Theory (1988), pp. 161?176."},{"key":"CR54","first-page":"43","volume":"50","author":"T. V. Wimer","year":"1985","unstructured":"T. V. Wimer, S. T. Hedetniemi, and R. Laskar, A methodology for constructing linear graph algorithms,Congressus Numerantium,50 (1985), 43?60.","journal-title":"Congressus Numerantium"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293664.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01293664\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:36:02Z","timestamp":1586180162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01293664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["BF01293664"],"URL":"https:\/\/doi.org\/10.1007\/bf01293664","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}