{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:43:53Z","timestamp":1777596233003,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,5,23]],"date-time":"2009-05-23T00:00:00Z","timestamp":1243036800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s10878-009-9230-0","type":"journal-article","created":{"date-parts":[[2009,5,22]],"date-time":"2009-05-22T17:58:46Z","timestamp":1243015126000},"page":"319-341","source":"Crossref","is-referenced-by-count":24,"title":["A parameterized perspective on packing paths of length two"],"prefix":"10.1007","volume":"18","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Raible","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,23]]},"reference":[{"key":"9230_CR1","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.dam.2004.07.003","volume":"146","author":"C Bazgan","year":"2005","unstructured":"Bazgan C, Hassin R, Monnot J (2005) Approximation algorithms for some vehicle routing problems. Discrete Appl Math 146:27\u201342","journal-title":"Discrete Appl Math"},{"key":"9230_CR2","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"KMJ Bontridder De","year":"2003","unstructured":"De Bontridder KMJ, Halld\u00f3rsson BV, Halld\u00f3rsson MM, Lenstra JK, Ravi R, Stougie L (2003) Approximation algorithms for the test cover problem. Math Program, Ser B 98:477\u2013491","journal-title":"Math Program, Ser B"},{"key":"9230_CR3","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J Chen","year":"2007","unstructured":"Chen J, Fernau H, Kanj YA, Xia G (2007) Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J Comput 37:1077\u20131108","journal-title":"SIAM J Comput"},{"key":"9230_CR4","unstructured":"Chen J, Fernau H, Ning D, Raible D, Wang J (2008) A parameterized perspective on P2-packings. Technical report 0804.0570, ArXiv, http:\/\/arxiv.org\/abs\/0804.0570"},{"key":"9230_CR5","first-page":"1","volume":"1","author":"C Cotta","year":"2002","unstructured":"Cotta C, Moscato P (2002) On the parameterized complexity of problems related with feature identification for gene expression data mining techniques. Bioinformatics 1:1\u20138","journal-title":"Bioinformatics"},{"key":"9230_CR6","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1016\/S0022-0000(03)00081-3","volume":"67","author":"C Cotta","year":"2003","unstructured":"Cotta C, Moscato P (2003) The k-feature set problem is W[2]-complete. J Comput Syst Sci 67:686\u2013690","journal-title":"J Comput Syst Sci"},{"key":"9230_CR7","series-title":"LNCS","first-page":"237","volume-title":"Software seminar SOFSEM","author":"F Dehne","year":"2006","unstructured":"Dehne F, Fellows M, Fernau H, Prieto E, Rosamond F (2006) Nonblocker: parameterized algorithmics for minimum dominating set. In: \u0160tuller J, Wiedermann J, Tel G, Pokorn\u00fd J, Bielikova M (eds) Software seminar SOFSEM. LNCS, vol 3831. Springer, Berlin, pp 237\u2013245"},{"key":"9230_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin"},{"key":"9230_CR9","series-title":"Texts in algorithmics","first-page":"1","volume-title":"Algorithms and complexity in Durham ACiD 2005","author":"V Estivill-Castro","year":"2005","unstructured":"Estivill-Castro V, Fellows MR, Langston MA, Rosamond FA (2005) FPT is P-time extremal structure I. In: Broersma H, Johnson M, Szeider S (eds) Algorithms and complexity in Durham ACiD 2005. Texts in algorithmics, vol 4. King\u2019s College, London, pp 1\u201341"},{"key":"9230_CR10","doi-asserted-by":"crossref","unstructured":"Fellows M (2002) Parameterized complexity: the main ideas and connections to practical computing. Electron Notes Theor Comput Sci 61","DOI":"10.1007\/3-540-36383-1_3"},{"key":"9230_CR11","unstructured":"Fernau H (2005) Parameterized algorithmics: a graph-theoretic approach. Habilitationsschrift, Universit\u00e4t T\u00fcbingen, Germany"},{"key":"9230_CR12","first-page":"69","volume-title":"Algorithms and complexity in Durham ACiD 2006","author":"H Fernau","year":"2006","unstructured":"Fernau H, Manlove DF (2006) Vertex and edge covers with clustering properties: Complexity and algorithms. In: Algorithms and complexity in Durham ACiD 2006. King\u2019s College, London, pp 69\u201384"},{"key":"9230_CR13","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/978-3-540-85097-7_6","volume-title":"Combinatorial optimization and applications COCOA","author":"H Fernau","year":"2008","unstructured":"Fernau H, Raible D (2008) A parameterized perspective on packing paths of length two. In: Yang B, Du D-Z, An Wang C (eds) Combinatorial optimization and applications COCOA. LNCS, vol 5165. Springer, Berlin, pp 54\u201363"},{"key":"9230_CR14","first-page":"133","volume":"2","author":"T Gallai","year":"1959","unstructured":"Gallai T (1959) \u00dcber extreme Punkt-und Kantenmengen. Ann Univ Sci Bp E\u00f6tv\u00f6s Sect Math 2:133\u2013138","journal-title":"Ann Univ Sci Bp E\u00f6tv\u00f6s Sect Math"},{"key":"9230_CR15","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0020-0190(97)00097-5","volume":"63","author":"R Hassin","year":"1997","unstructured":"Hassin R, Rubinstein S (1997) An approximation algorithm for maximum packing of 3-edge paths. Inf Process Lett 63:63\u201367","journal-title":"Inf Process Lett"},{"key":"9230_CR16","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.dam.2005.11.003","volume":"154","author":"R Hassin","year":"2006","unstructured":"Hassin R, Rubinstein S (2006) An approximation algorithm for maximum triangle packing. Discrete Appl Math 154:971\u2013979; 2620 [Erratum]","journal-title":"Discrete Appl Math"},{"key":"9230_CR17","unstructured":"Hell P, Kirkpatrick DG (1982) Star factors and star packings. Technical report 82-6, Computing Science, Simon Fraser University, Burnaby, BC V5A1S6, Canada"},{"issue":"4","key":"9230_CR18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft JE, Karp RM (1973) An n 5\/2-algorithm for maximum matchings in bipartite graphs. SIAM J Comput 2(4):225\u2013231","journal-title":"SIAM J Comput"},{"key":"9230_CR19","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot S, Raman V (2002) Parameterized complexity of finding subgraphs with hereditary properties. Theor Comput Sci 289:997\u20131008","journal-title":"Theor Comput Sci"},{"key":"9230_CR20","doi-asserted-by":"crossref","unstructured":"Kirkpatrick DG, Hell P (1978) On the completeness of a generalized matching problem. In: ACM symposium on theory of computing STOC, pp. 240\u2013245","DOI":"10.1145\/800133.804353"},{"key":"9230_CR21","series-title":"DMTCS proceedings, Discrete mathematics and theoretical computer science","first-page":"213","volume-title":"2005 European conference on combinatorics, graph theory and applications (EuroComb \u201905)","author":"A Kosowski","year":"2005","unstructured":"Kosowski A, Ma\u0142afiejski M, \u017byli\u0144ski P (2005) Packing three-vertex paths in a subcubic graph. In: Felsner S (ed) 2005 European conference on combinatorics, graph theory and applications (EuroComb \u201905). DMTCS proceedings, Discrete mathematics and theoretical computer science, vol AE. Springer, Berlin, pp 213\u2013218"},{"key":"9230_CR22","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, languages and programming, 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7\u201311, 2008, Proceedings, Part I: Tack A: algorithms, automata, complexity, and games","author":"I Koutis","year":"2008","unstructured":"Koutis I (2008) Faster algebraic algorithms for path and packing problems. In: Aceto L, Damg\u00e5rd I, Ann Goldberg L, Halld\u00f3rsson MM, Ing\u00f3lfsd\u00f3ttir A, Walukiewicz I (eds) Automata, languages and programming, 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7\u201311, 2008, Proceedings, Part I: Tack A: algorithms, automata, complexity, and games. Lecture notes in computer science, vol 5125. Springer, Berlin, pp 575\u2013586"},{"key":"9230_CR23","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/11847250_8","volume-title":"International workshop on parameterized and exact computation IWPEC","author":"Y Liu","year":"2006","unstructured":"Liu Y, Lu S, Chen J, Sze S-H (2006) Greedy localization and color-coding: improved matching and packing algorithms. In: Bodlaender HL, Langston M (eds) International workshop on parameterized and exact computation IWPEC. LNCS, vol 4169. Springer, Berlin, pp 84\u201395"},{"key":"9230_CR24","first-page":"17","volume-title":"Symposium on foundations of computer science","author":"S Micali","year":"1980","unstructured":"Micali S, Vazirani VV (1980) An $\\mathcal{O}(\\sqrt{|V|}|E|)$ algorithm for finding maximum matchings in general graphs. In: Symposium on foundations of computer science. IEEE Press, New York, pp 17\u201327"},{"key":"9230_CR25","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/978-3-540-69507-3_36","volume-title":"Software seminar SOFSEM 2008","author":"J Monnot","year":"2007","unstructured":"Monnot J, Toulouse S (2007) The P k partitioning problem and related problems in bipartite graphs. In: van Leeuwen J (eds) Software seminar SOFSEM 2008. Lecture notes in computer science, vol 4362. Springer, Berlin, pp 422\u2013433"},{"key":"9230_CR26","series-title":"LNCS","first-page":"401","volume-title":"Software seminar SOFSEM","author":"H Moser","year":"2009","unstructured":"Moser H (2009) A problem kernelization for graph packing. In: Nielsen M (eds) Software seminar SOFSEM. LNCS, vol 5404. Springer, Berlin, pp 401\u2013412"},{"key":"9230_CR27","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0012-365X(84)90170-5","volume":"49","author":"J Plesn\u00edk","year":"1984","unstructured":"Plesn\u00edk J (1984) Equivalence between the minimum covering problem and the maximum matching problem. Discrete Math 49:315\u2013317","journal-title":"Discrete Math"},{"key":"9230_CR28","series-title":"LNCS","first-page":"465","volume-title":"Proceedings of WADS 2003, workshop on algorithms and data structures","author":"E Prieto","year":"2003","unstructured":"Prieto E, Sloper C (2003) Either\/or: Using vertex cover structure in designing FPT-algorithms\u2014the case of k-internal spanning tree. In: Proceedings of WADS 2003, workshop on algorithms and data structures. LNCS, vol 2748. Springer, Berlin, pp 465\u2013483"},{"key":"9230_CR29","series-title":"LNCS","first-page":"138","volume-title":"International workshop on parameterized and exact computation IWPEC 2004","author":"E Prieto","year":"2004","unstructured":"Prieto E, Sloper C (2004) Looking at the stars. In: Downey R, Fellows M, Dehne F (eds) International workshop on parameterized and exact computation IWPEC 2004. LNCS, vol 3162. Springer, Berlin, pp 138\u2013148"},{"key":"9230_CR30","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-540-79228-4_7","volume-title":"Theory and applications of models of computation TAMC","author":"J Wang","year":"2008","unstructured":"Wang J, Feng Q (2008) An O *(3.523k ) parameterized algorithm for 3-set packing. In: Agrawal M (eds) Theory and applications of models of computation TAMC. LNCS, vol 4978. Springer, Berlin, pp 82\u201393"},{"key":"9230_CR31","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/978-3-540-79228-4_19","volume-title":"Theory and applications of models of computation TAMC","author":"J Wang","year":"2008","unstructured":"Wang J, Ning D, Feng Q, Chen J (2008) An improved parameterized algorithm for a generalized matching problem. In: Agrawal M (eds) Theory and applications of models of computation TAMC. LNCS, vol 4978. Springer, Berlin, pp 212\u2013222"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9230-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9230-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9230-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9230-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,23]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9230"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9230-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,23]]}}}