{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:40Z","timestamp":1759637620726},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405450"},{"type":"electronic","value":"9783540450788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45078-8_41","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T17:23:52Z","timestamp":1277227432000},"page":"474-483","source":"Crossref","is-referenced-by-count":28,"title":["Either\/Or: Using Vertex Cover Structure in Designing FPT-Algorithms \u2014 the Case of k-Internal Spanning Tree"],"prefix":"10.1007","author":[{"given":"Elena","family":"Prieto","sequence":"first","affiliation":[]},{"given":"Christian","family":"Sloper","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"41_CR1","unstructured":"Abu-Khzam, F.: Private communication"},{"key":"41_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 613\u2013627. Springer, Heidelberg (2002)"},{"issue":"3","key":"41_CR3","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Fellows, M.R., Raman, V.: An Improved Fixed Parameter Algorithm for Vertex Cover. Information Processing Letters\u00a065(3), 163\u2013168 (1998)","journal-title":"Information Processing Letters"},{"key":"41_CR4","unstructured":"Chor, B., Fellows, M., Juedes, D.: Private communication concerning (manuscript) (in preparation)"},{"key":"41_CR5","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R., Fellows, M.: The parameterized complexity of short computation and factorization. Archive for Mathematical Logic\u00a036, 321\u2013338 (1997)","journal-title":"Archive for Mathematical Logic"},{"key":"41_CR6","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I., Jia, W.: Vertex cover: Further Observations and Further Improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"41_CR7","unstructured":"Cormen, T.H., Leierson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge"},{"key":"41_CR8","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Parameterized Computational Feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkhauser, Boston (1995)"},{"key":"41_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness II: completeness for W[1]. Theoretical Computer Science A\u00a0141, 109\u2013131 (1995)","journal-title":"Theoretical Computer Science A"},{"key":"41_CR10","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1998","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Graham, R., Kratochvil, J., Nesetril, J., Roberts, F. (eds.) Contemporary Trends in Discrete Mathematics. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a049, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"41_CR12","unstructured":"Faisal, A., Fellows, M., Langston, M., Rosamond, F.: Private communication concerning (manuscript) (in preparation)"},{"key":"41_CR13","unstructured":"Fellows, M., McCartin, C., Rosamond, F., Stege, U.: Spanning Trees with Few and Many Leaves (to appear)"},{"key":"41_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G. Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F., Morzenti, A.: A Short Note on the Approximability of the Maximum Leaves Spanning Tree Problem. Information Processing Letters\u00a052, 45\u201349 (1994)","journal-title":"Information Processing Letters"},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(96)00265-4","volume":"181","author":"G. Galbiati","year":"1997","unstructured":"Galbiati, G., Morzenti, A., Maffioli, F.: On the Approximability of some Maximum Spanning Tree Problems. Theoretical Computer Science\u00a0181, 107\u2013118 (1997)","journal-title":"Theoretical Computer Science"},{"key":"41_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)"},{"key":"41_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/3-540-44968-X_14","volume-title":"Computing and Combinatorics","author":"S. Khot","year":"2000","unstructured":"Khot, S., Raman, V.: Parameterized Complexity of Finding Hereditary Properties. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol.\u00a01858, p. 137. Springer, Heidelberg (2000); Theoretical Computer Science (COCOON 2000 special issue)"},{"key":"41_CR18","unstructured":"Langston, M.: Private communication"},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H.-I. Lu","year":"1998","unstructured":"Lu, H.-I., Ravi, R.: Approximating Maximum Leaf Spanning Trees in Almost Linear Time. Journal of Algorithms\u00a029, 132\u2013141 (1998)","journal-title":"Journal of Algorithms"},{"key":"41_CR20","unstructured":"McCartin, C.: Ph.D. dissertation in Computer Science, Victoria University, Wellington, New Zealand (2003)"},{"key":"41_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"STACS 99","author":"R. Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: Upper Bounds for Vertex Cover Further Improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 561\u2013570. Springer, Heidelberg (1999)"},{"key":"41_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/3-540-57155-8_284","volume-title":"Algorithms and Data Structures","author":"J.A. Telle","year":"1993","unstructured":"Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 610\u2013621. Springer, Heidelberg (1993)"},{"key":"41_CR23","unstructured":"Robertson, N., Seymor, P.D.: Graph Minors. XX Wagner\u2019s conjecture (to appear)"},{"key":"41_CR24","unstructured":"Stege, U.: Ph.D. dissertation in Computer Science, ETH, Zurich, Switzerland (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45078-8_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T21:26:57Z","timestamp":1552598817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45078-8_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405450","9783540450788"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45078-8_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}