{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:21:57Z","timestamp":1725488517456},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424239"},{"type":"electronic","value":"9783540446347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44634-6_8","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:20:48Z","timestamp":1186726848000},"page":"75-86","source":"Crossref","is-referenced-by-count":4,"title":["Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover"],"prefix":"10.1007","author":[{"given":"Naomi","family":"Nishimura","sequence":"first","affiliation":[]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Stefan Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability-A survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"R. Balasubramanian, Michael Fellows, and Venkatesh Raman. An improved fixed-parameter algorithm for vertex cover. Inform. Proc. Letters, 65:163\u2013168, 1998.","journal-title":"Inform. Proc. Letters"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. F. Buss","year":"1993","unstructured":"Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P. SIAM J. Computing, 22:560\u2013572, 1993.","journal-title":"SIAM J. Computing"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0095-8956(91)90068-U","volume":"52","author":"D. Bienstock","year":"1991","unstructured":"Daniel Bienstock, Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a forest. J. Comb. Theory Series B, 52:274\u2013283, 1991.","journal-title":"J. Comb. Theory Series B"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Proc. Letters, 58:171\u2013176, 1996.","journal-title":"Inform. Proc. Letters"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L. Cai","year":"1997","unstructured":"Liming Cai, Jianer Chen, Rodney Downey, and Michael Fellows. Advice classes of parameterized tractability. Annals of Pure and Applied Logic, 84:119\u2013138, 1997.","journal-title":"Annals of Pure and Applied Logic"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"J. Chen, I.A. Kanj, and W. Jia. Vertex cover: Further observations and further improvements. In Proceedings of the 25th International Workshop on Graph-Theoretical Concepts in Computer Science, pages 313\u2013324. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-46784-X_30"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. G. Downey","year":"1995","unstructured":"Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput., 24:873\u2013921, 1995.","journal-title":"SIAM J. Comput."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"8_CR10","first-page":"73","volume":"69","author":"R. G. Downey","year":"1999","unstructured":"Rodney G. Downey, Michael R. Fellows, and Ulrike Stege. Computational tractability: the view from Mars. Bulletin of the European Association of Theoretical Computer Science, 69:73\u201397, 1999.","journal-title":"Bulletin of the European Association of Theoretical Computer Science"},{"key":"8_CR11","unstructured":"Michael J. Dinneen. Bounded Combinatorial Width and Forbidden Substructures. PhD thesis, Department of Computer Science, University of Victoria, 1995."},{"issue":"11","key":"8_CR12","first-page":"1199","volume":"3","author":"M. J. Dinneen","year":"1997","unstructured":"Michael J. Dinneen. Too many minor order obstructions (for parametrized lower ideals). Journal of Universal Computer Science, 3(11):1199\u20131206, 1997.","journal-title":"Journal of Universal Computer Science"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M. R. Fellows","year":"1988","unstructured":"Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. J. ACM, 35:727\u2013739, 1988.","journal-title":"J. ACM"},{"issue":"3","key":"8_CR14","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"M. R. Fellows","year":"1994","unstructured":"Michael R. Fellows and Michael A. Langston. On search, decision, and the efficiency of polynomial-time algorithms. J. Comp. Syst. Sc., 49(3):769\u2013779, 1994.","journal-title":"J. Comp. Syst. Sc."},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M. Farach","year":"1995","unstructured":"Martin Farach, Teresa Przytycka, and Mikkel Thorup. On the agreement of many trees. Inform. Proc. Letters, 55:297\u2013301, 1995.","journal-title":"Inform. Proc. Letters"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1090\/conm\/065\/891251","volume":"65","author":"H. Friedman","year":"1987","unstructured":"Harvey Friedman, Neil Robertson, and Paul D. Seymour. The metamathe-matics of the graph minor theorem. Contemporary Mathematics, 65:229\u2013261, 1987.","journal-title":"Contemporary Mathematics"},{"issue":"5","key":"8_CR17","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"Haim Kaplan, Ron Shamir, and Robert E. Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput., 28(5):1906\u20131922, 1999.","journal-title":"SIAM J. Comput."},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Jens Lagergren. An upper bound on the size of an obstruction. In Neil Robertson and Paul Seymour, editors, Graph Structure Theory, Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, Seattle WA, June 1991, pages 601\u2013621, Providence, RI, 1993. American Math. Soc. Contemp. Math. 147.","DOI":"10.1090\/conm\/147\/01202"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1006\/jctb.1997.1788","volume":"73","author":"J. Lagergren","year":"1998","unstructured":"Jens Lagergren. Upper bounds on the size of obstructions and intertwines. J. Combin. Theory Ser. B, 73:7\u201340, 1998.","journal-title":"J. Combin. Theory Ser. B"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J. M. Lewis","year":"1980","unstructured":"J. M. Lewis and Christos H. Papadimitriou. The node-deletion problem for hereditary properties is NP-complete. J. Comp. Syst. Sc., 20:219\u2013230, 1980.","journal-title":"J. Comp. Syst. Sc."},{"issue":"1\u20133","key":"8_CR21","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0012-365X(97)00147-7","volume":"182","author":"M. A. Langston","year":"1998","unstructured":"Michael A Langston and Barbara C. Plaut. On algorithmic applications of the immersion order. An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory. Discrete Mathematics, 182(1\u20133):191\u2013196, 1998.","journal-title":"Discrete Mathematics"},{"key":"8_CR22","series-title":"Data Structures and Algorithms","volume-title":"Graph Algorithms and NP-Completeness","author":"K. Mehlhorn","year":"1984","unstructured":"Kurt Mehlhorn. Graph Algorithms and NP-Completeness, volume 2 of Data Structures and Algorithms. Springer Verlag, Berlin, 1984."},{"issue":"2","key":"8_CR23","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"Meena Mahajan and Venkatesh Raman","year":"1999","unstructured":"Meena Mahajan and Venkatesh Raman. Parameterizing above guaranteed values: maxsat and maxcut. J. Algorithms, 31(2):335\u2013354, May 1999.","journal-title":"J. Algorithms"},{"key":"8_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-49477-4_12","volume-title":"Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM\u201998)","author":"R. Niedermeier","year":"1998","unstructured":"Rolf Niedermeier. Some prospects for efficient fixed parameter algorithms. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM\u201998), volume 1521 of Lecture Notes in Computer Science, pages 168\u2013185, 1998."},{"key":"8_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS\u201999)","author":"R. Niedermeier","year":"1999","unstructured":"Rolf Niedermeier and Peter Rossmanith. Upper bounds for vertex cover further improved. In C. Meinel, S. Tison, editors, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS\u201999), volume 1563 of Lecture Notes in Computer Science, pages 561\u2013570, 1999."},{"key":"8_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-59071-4_34","volume-title":"Proceedings 20th International Workshop on Graph Theoretic Concepts in Computer Science WG\u201994","author":"S. Ramachandramurthi","year":"1995","unstructured":"Siddharthan Ramachandramurthi. A lower bound for treewidth and its consequences. In Ernst W. Mayr, Gunther Schmidt, and Gottfried Tinhofer, editors, Proceedings 20th International Workshop on Graph Theoretic Concepts in Computer Science WG\u201994, volume 903 of Lecture Notes in Computer Science, pages 14\u201325. Springer Verlag, 1995."},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"Neil Robertson and Paul D. Seymour. Disjoint paths-A survey. SIAM J. Alg. Disc. Meth., 6:300\u2013305, 1985.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors \u2014 A survey. In I. Anderson, editor, Surveys in Combinatorics, pages 153\u2013171. Cambridge Univ. Press, 1985.","DOI":"10.1017\/CBO9781107325678.009"},{"key":"8_CR29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B, 63:65\u2013110, 1995.","journal-title":"J. Comb. Theory Series B"},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(00)00175-X","volume":"105","author":"D. M. Thilikos","year":"2000","unstructured":"Dimitrios M. Thilikos. Algorithms and obstructions for linear-width and related search parameters. Discrete Applied Mathematics, 105:239\u2013271, 2000.","journal-title":"Discrete Applied Mathematics"},{"issue":"1\/3","key":"8_CR31","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(94)90092-2","volume":"127","author":"A. Takahashi","year":"1994","unstructured":"Atsushi Takahashi, Shuichi Ueno, and Yoji Kajitani. Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Discrete Mathematics, 127(1\/3):293\u2013304, 1994.","journal-title":"Discrete Mathematics"},{"key":"8_CR32","doi-asserted-by":"crossref","unstructured":"Jan van Leeuwen. Graph algorithms. In Handbook of Theoretical Computer Science, A: Algorithms and Complexity Theory, pages 527\u2013631, Amsterdam, 1990. North Holland Publ. Comp.","DOI":"10.1016\/B978-0-444-88071-0.50015-1"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44634-6_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:12:19Z","timestamp":1556734339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44634-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424239","9783540446347"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-44634-6_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}