{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:55Z","timestamp":1761611215104},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_19","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"240-251","source":"Crossref","is-referenced-by-count":10,"title":["Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems"],"prefix":"10.1007","author":[{"given":"R. Fellows","family":"Michael","sequence":"first","affiliation":[]},{"given":"Catherine","family":"McCartin","sequence":"additional","affiliation":[]},{"given":"A. Rosamond","family":"Frances","sequence":"additional","affiliation":[]},{"given":"Ulrike","family":"Stege","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"19_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/3-540-51542-9_48","volume-title":"On linear time minor tests and depth-first search","author":"H. L. Bodlaender","year":"1989","unstructured":"H. L. Bodlaender. \u201cOn linear time minor tests and depth-first search.\u201d In F. Dehne et al. (eds.), Proc. First Workshop on Algorithms and Data Structures, LNCS 382, pp. 577\u2013590, 1989."},{"issue":"3","key":"19_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, M. R. Fellows, and V. Raman. \u201cAn Improved Fixed-Parameter Algorithm for Vertex Cover.\u201d Information Processing Letters 65:3, pp. 163\u2013168, 1998.","journal-title":"Information Processing Letters"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"B. Berger, T. Leighton. \u201cProtein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete.\u201d In S. Istrail, P. Pevzner, and M. Waterman (eds.), Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB98), pp. 30\u201339, 1998.","DOI":"10.1089\/cmb.1998.5.27"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"[CCDF97] L. Cai, J. Chen, R. Downey, and M. Fellows. \u201cThe parameterized complexity of short computation and factorization.\u201d Archive for Mathematical Logic 36, pp. 321\u2013338, 1997.","journal-title":"Archive for Mathematical Logic"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni and M. Yan-nakakis. \u201cOn the complexity of protein folding.\u201d In S. Istrail, P. Pevzner, and M. Waterman (eds.), Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB98), 1998.","DOI":"10.1089\/cmb.1998.5.423"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"J. Chen, I. Kanj, and W. Jia. \u201cVertex cover: Further Observations and Further Improvements.\u201d 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201999) Ascona, Switzerland, June 1999.","DOI":"10.1007\/3-540-46784-X_30"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows. \u201cParameterized Computational Feasibility.\u201d P. Clote, J. Remmel (eds.): Feasible Mathematics II Boston: Birkhauser, pp. 219\u2013244, 1995.","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R. Downey","year":"1995","unstructured":"R. Downey and M. Fellows. \u201cFixed-parameter tractability and completeness II: completeness for W[1].\u201d Theoretical Computer Science A 141, pp. 109\u2013131, 1995.","journal-title":"Theoretical Computer Science A"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"R. Downey, M. Fellows, and U. Stege. \u201cParameterized complexity: a framework for systematically confronting computational intractability.\u201d In: Contemporary Trends in Discrete Mathematics (R. Graham, J. Kratochvil, J. Nesetril and F. Roberts, eds.), AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 49, pp. 49\u201399, 1999.","DOI":"10.1090\/dimacs\/049\/04"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E. Dijkstra","year":"1974","unstructured":"E. Dijkstra. \u201cSelf-Stabilizing Systems in Spite of Distributed Control.\u201d Communications of the ACM 17, pp. 643\u2013644, 1974.","journal-title":"Communications of the ACM"},{"key":"19_CR12","unstructured":"M. Fellows and M. Langston. \u201cOn Well-Partial-Order Theory and Its Applications to Combinatorial Problems of VLSI Design.\u201d Technical Report CS-88-188, Department of Computer Science, Washington State University, 1988."},{"key":"19_CR13","unstructured":"M. Fellows, C. McCartin, F. Rosamond, and U. Stege. \u201cThe parametric dual of Dominating Set is fixed-parameter tractable,\u201d 2000."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G. Galbiati","year":"1994","unstructured":"G. Galbiati, F. Maffioli, and A. Morzenti. \u201cA Short Note on the Approxima-bility of the Maximum Leaves Spanning Tree Problem.\u201d Information Processing Letters 52, pp. 45\u201349, 1994.","journal-title":"Information Processing Letters"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(96)00265-4","volume":"181","author":"G. Galbiati","year":"1997","unstructured":"G. Galbiati, A. Morzenti and F. Maffioli. \u201cOn the Approximability of some Maximum Spanning Tree Problems.\u201d Theoretical Computer Science 181, pp. 107\u2013118, 1997.","journal-title":"Theoretical Computer Science"},{"key":"19_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, 1979."},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"T. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc, 1998.","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"19_CR18","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Graph-theoretic concepts in computer science","author":"E. Kranakis","year":"1995","unstructured":"E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia, G. Woeginger. \u201cVC-dimensions for graphs.\u201d In M. Nagl, editor, Graph-theoretic concepts in computer science, LNCS 1017, pp. 1\u201313, 1995."},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H.-I. Lu","year":"1998","unstructured":"H.-I. Lu and R. Ravi. \u201cApproximating Maximum Leaf Spanning Trees in Almost Linear Time.\u201d Journal of Algorithms 29, pp. 132\u2013141, 1998.","journal-title":"Journal of Algorithms"},{"key":"19_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"Upper Bounds for Vertex Cover Further Improved","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith. \u201cUpper Bounds for Vertex Cover Further Improved.\u201d In C. Meinel and S. Tison, editors, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, LNCS 1563, pp. 561\u2013570, 1999."},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"R. Niedermeier and P. Rossmanith. \u201cA General Method to Speed Up Fixed-Parameter-Tractable Algorithms.\u201d Information Processing Letters, 73, pp. 125\u2013129, 2000.","journal-title":"Information Processing Letters"},{"key":"19_CR22","unstructured":"R. Niedermeier and P. Rossmanith. \u201cAn efficient fixed parameter algorithm for 3-Hitting Set.\u201d accepted for publication in Journal of Discrete Algorithms, August 2000."},{"key":"19_CR23","volume-title":"Resolving Conflicts from Computational Biology","author":"U. Stege","year":"1999","unstructured":"U. Stege. Resolving Conflicts from Computational Biology. Ph.D. thesis, Department of Computer Science, ETH Z\u00fcrich, Switzerland, 1999."}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T22:37:26Z","timestamp":1587854246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}