{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T07:18:02Z","timestamp":1712301482878},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,12,12]],"date-time":"2012-12-12T00:00:00Z","timestamp":1355270400000},"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":[[2014,10]]},"DOI":"10.1007\/s10878-012-9575-7","type":"journal-article","created":{"date-parts":[[2012,12,11]],"date-time":"2012-12-11T16:50:18Z","timestamp":1355244618000},"page":"674-691","source":"Crossref","is-referenced-by-count":2,"title":["Efficient algorithms for the max\u00a0 $$k$$ -vertex cover problem"],"prefix":"10.1007","volume":"28","author":[{"given":"Federico","family":"Della Croce","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,12]]},"reference":[{"issue":"2","key":"9575_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable graphs. J Algorithms 12(2):308\u2013340","journal-title":"J Algorithms"},{"issue":"2","key":"9575_CR2","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund A, Husfeldt T, Koivisto M (2009) Set partitioning via inclusion\u2013exclusion. SIAM J Comput 39(2):546\u2013563","journal-title":"SIAM J Comput"},{"issue":"6","key":"9575_CR3","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0020-0190(02)00434-9","volume":"85","author":"M Bl\u00e4ser","year":"2003","unstructured":"Bl\u00e4ser M (2003) Computing small partial coverings. Inform Process Lett 85(6):327\u2013331","journal-title":"Inform Process Lett"},{"key":"9575_CR4","unstructured":"Bourgeois N, Escoffier B, Th Paschos V (2007) Efficient approximation by \u201clow-complexity\u201d exponential algorithms. Cahier du LAMSADE 271, LAMSADE, Universit\u00e9 Paris-Dauphine, Paris. http:\/\/www.lamsade.dauphine.fr\/cahiers\/PDF\/cahierLamsade271.pdf"},{"key":"9575_CR5","doi-asserted-by":"crossref","unstructured":"Bourgeois N, Escoffier B, Th Paschos V (2009a) Efficient approximation of combinatorial problems by moderately exponential algorithms. In: Dehne F, Gavrilova M, Sack J-R, T\u00f3th CD (eds) Proceedings of algorithms and data structures symposium. Lecture notes in computer science, vol 5664. Springer, New York, pp 507\u2013518","DOI":"10.1007\/978-3-642-03367-4_44"},{"key":"9575_CR6","doi-asserted-by":"crossref","unstructured":"Bourgeois N, Escoffier B, Th Paschos V (2009b) Efficient approximation of min coloring by moderately exponential algorithms. Inform Process Lett 109(16):950\u2013954","DOI":"10.1016\/j.ipl.2009.05.002"},{"key":"9575_CR7","doi-asserted-by":"crossref","unstructured":"Bourgeois N, Escoffier B, Th Paschos V (2009c) Efficient approximation of min set cover by moderately exponential algorithms. Theor Comput Sci 410(21\u201323):2184\u20132195","DOI":"10.1016\/j.tcs.2009.02.007"},{"key":"9575_CR8","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks RL (1941) On coloring the nodes of a network. Math Proc Camb Philos Soc 37:194\u2013197","journal-title":"Math Proc Camb Philos Soc"},{"key":"9575_CR9","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai L (2008) Parameter complexity of cardinality constrained optimization problems. Comput J 51:102\u2013121","journal-title":"Comput J"},{"key":"9575_CR10","doi-asserted-by":"crossref","unstructured":"Cai L, Huang X (2006) Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender HL, Langston MA (eds) Proceedings of international workshop on parameterized and exact computation, IWPEC\u201906. Lecture notes in computer science, vol 4169. Springer, Zurich, pp 96\u2013108","DOI":"10.1007\/11847250_9"},{"key":"9575_CR11","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen J, Kanj IA, Jia W (2001) Vertex cover: further observations and further improvements. J Algorithms 41:280\u2013301","journal-title":"J Algorithms"},{"issue":"40\u201342","key":"9575_CR12","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40\u201342):3736\u20133756","journal-title":"Theor Comput Sci"},{"key":"9575_CR13","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle B (1990) The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform Comput 85:12\u201375","journal-title":"Inform Comput"},{"issue":"16","key":"9575_CR14","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M Cygan","year":"2009","unstructured":"Cygan M, Kowalik L, Wykurz M (2009) Exponential-time approximation of weighted set cover. Inform Process Lett 109(16):957\u2013961","journal-title":"Inform Process Lett"},{"issue":"40\u201342","key":"9575_CR15","doi-asserted-by":"crossref","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan M, Pilipczuk M (2010) Exact and approximate bandwidth. Theor Comput Sci 411(40\u201342):3701\u20133713","journal-title":"Theor Comput Sci"},{"key":"9575_CR16","unstructured":"Della Croce F, Paschos VT (2012) Efficient algorithms for the max k-vertex cover problem. In: Baeten JCM , Ball T, De Boer FS (eds) Proceedings of TCS 2012, Lecture notes in computer science, vol 7604. Springer, New York, pp. 36\u201348"},{"key":"9575_CR17","doi-asserted-by":"crossref","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. In: Monographs in computer science. Springer, New York","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9575_CR18","doi-asserted-by":"crossref","unstructured":"Downey RG, Fellows MR, McCartin C (2006) Parameterized approximation problems. In: Bodlaender HL, Langston MA (eds) Proceedings of international workshop on parameterized and exact computation, IWPEC\u201906. Lecture notes in computer science, vol 4169. Springer, New York, pp 121\u2013129","DOI":"10.1007\/11847250_11"},{"issue":"2","key":"9575_CR19","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige U, Langberg M (2001) Approximation algorithms for maximization problems arising in graph partitioning. J Algorithms 41(2):174\u2013211","journal-title":"J Algorithms"},{"key":"9575_CR20","doi-asserted-by":"crossref","unstructured":"Fellows MR (2009) Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Fiala J, Kratochv\u00edl J, Miller M (eds) Proceedings of international workshop on combinatorial algorithms, IWOCA\u201909. Lecture notes in computer science, vol 5874. Springer, New York, pp 2\u201310","DOI":"10.1007\/978-3-642-10217-2_2"},{"key":"9575_CR21","doi-asserted-by":"crossref","unstructured":"Fellows MR, Lokshtanov D, Misra N, Rosamond FA, Saurabh S (2008) Graph layout problems parameterized by vertex cover. In: Hong S-H, Nagamochi H, Fukunaga T (eds) Proceedings of international symposium on algorithms and computation, ISAAC\u201908. Lecture notes in computer science, vol 5369. Springer, New York, pp 294\u2013305","DOI":"10.1007\/978-3-540-92182-0_28"},{"issue":"5","key":"9575_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin FV, Grandoni F, Kratsch D (2009) A measure and conquer approach for the analysis of exact algorithms. J Assoc Comput Mach 56(5):1\u201332","journal-title":"J Assoc Comput Mach"},{"issue":"5","key":"9575_CR23","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"FV Fomin","year":"2006","unstructured":"Fomin FV, H\u00f8ie K (2006) Pathwidth of cubic graphs and exact algorithms. Inform Process Lett 97(5):191\u2013196","journal-title":"Inform Process Lett"},{"issue":"16","key":"9575_CR24","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1016\/j.ipl.2011.05.016","volume":"111","author":"FV Fomin","year":"2011","unstructured":"Fomin FV, Lokshtanov D, Raman V, Saurabh S (2011) Subexponential algorithms for partial cover problems. Inform Process Lett 111(16):814\u2013818","journal-title":"Inform Process Lett"},{"key":"9575_CR25","unstructured":"Fomin FV, Villanger Y (2008) Treewidth computation and extremal combinatorics. In: Aceto L, Damgaard I, Goldberg LA, Halld\u00f3rsson MM, Ingolfsdottir A, Walukiewicz I (eds) Proceedings of ICALP\u201908. Lecture notes in computer science, vol 5125. Springer, New York, pp 210\u2013221"},{"key":"9575_CR26","doi-asserted-by":"crossref","unstructured":"F\u00fcrer M, Gaspers S, Kasiviswanathan SP (2009) An exponential time 2-approximation algorithm for bandwidth. In: Proceedings of international workshop on parameterized and exact computation, IWPEC\u201909, Lecture notes in computer science, vol 5917. Springer, New York, pp 173\u2013184","DOI":"10.1007\/978-3-642-11269-0_14"},{"key":"9575_CR27","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H, Freeman, San Francisco"},{"key":"9575_CR28","doi-asserted-by":"crossref","unstructured":"Guo J, Niedermeier R, Wernicke S (2005) Parameterized complexity of generalized vertex cover problems. In: Dehne F, L\u00f3pez-Ortiz A, Sack J-R (eds) Proceedings of Iiternational workshop on algorithms and data structures, WADS\u201905. Lecture notes in computer science, vol 3608. Springer, New York, pp 36\u201348","DOI":"10.1007\/11534273_5"},{"issue":"4","key":"9575_CR29","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512\u2013530","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"9575_CR30","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10878-005-2269-7","volume":"10","author":"G J\u00e4ger","year":"2005","unstructured":"J\u00e4ger G, Srivastav A (2005) Improved approximation algorithms for maximum graph partitioning problems. J Comb Optim 10(2):133\u2013167","journal-title":"J Comb Optim"},{"key":"9575_CR31","doi-asserted-by":"crossref","unstructured":"Kneis J, Langer A, Rossmanith P (2008) Improved upper bounds for partial vertex cover. In: Hajo B, Thomas E, Tom F, Daniel P (eds) Proceedings of international workshop on graph theoretical concepts in computer science, WG\u201908. Lecture notes in computer science, vol 5344. Springer, New York, pp 240\u2013251","DOI":"10.1007\/978-3-540-92248-3_22"},{"key":"9575_CR32","unstructured":"Lingo (2010) 2.0- Optimization modeling software for linear, nonlinear, and integer programming. LINDO Systems, Chicago. http:\/\/www.lindo.com\/index.php"},{"issue":"1","key":"9575_CR33","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx D (2008) Parameterized complexity and approximation algorithms. Comput J 51(1):60\u201378","journal-title":"Comput J"},{"key":"9575_CR34","unstructured":"Marx D (2010) Fixed parameter algorithms. Open lectures for PhD students in computer science. Harvard University Press, Cambridge"},{"key":"9575_CR35","unstructured":"Moser H (2005) Exact algorithms for generalizations of vertex cover. Master\u2019s thesis, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Jena"},{"key":"9575_CR36","unstructured":"Ne\u0161et\u0159il J, Poljak S (1985) On the complexity of the subgraph problem. Comment Math Univ Carolinae 26: 415\u2013419"},{"issue":"2","key":"9575_CR37","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier R, Rossmanith P (2003) On efficient fixed-parameter algorithms for weighted vertex cover. J Algorithms 47(2):63\u201377","journal-title":"J Algorithms"},{"key":"9575_CR38","unstructured":"Praveen M (2010) Logic Courcelle\u2019s theorem and application. IMPECS School on Parameterized and Exact Computation, Chennai"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9575-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-012-9575-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9575-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,6]],"date-time":"2019-07-06T19:14:20Z","timestamp":1562440460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9575-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,12]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["9575"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9575-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,12]]}}}