{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T13:57:44Z","timestamp":1778680664122,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2014,8,3]],"date-time":"2014-08-03T00:00:00Z","timestamp":1407024000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s00236-014-0204-z","type":"journal-article","created":{"date-parts":[[2014,8,2]],"date-time":"2014-08-02T02:32:40Z","timestamp":1406946760000},"page":"473-497","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Parameterized complexity of three edge contraction problems with degree constraints"],"prefix":"10.1007","volume":"51","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,3]]},"reference":[{"issue":"2","key":"204_CR1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(83)90012-0","volume":"26","author":"T Asano","year":"1983","unstructured":"Asano, T., Hirata, T.: Edge-contraction problems. J. Comput. Syst. Sci. 26(2), 197\u2013208 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"204_CR2","doi-asserted-by":"crossref","unstructured":"Belmonte, R., Golovach, P. A., van \u2019t Hof, P., Paulusma, D.: Parameterized complexity of two edge contraction problems with degree constraints. In: IPEC 2013, LNCS 8246, pp. 16\u201327. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03898-8_3"},{"key":"204_CR3","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"AE Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. J. Graph Theory 11, 71\u201379 (1987)","journal-title":"J. Graph Theory"},{"issue":"1","key":"204_CR4","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J. 51(1), 102\u2013121 (2008)","journal-title":"Comput. J."},{"key":"204_CR5","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/S0097539793258295","volume":"26","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On the amount of nondeterminism and the power of verifying. SIAM J. Comput. 26, 733\u2013750 (1997)","journal-title":"SIAM J. Comput."},{"key":"204_CR6","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/inco.1995.1156","volume":"123","author":"L Cai","year":"1995","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the structure of parameterized problems in NP. Inf. Comput. 123, 38\u201349 (1995)","journal-title":"Inf. Comput."},{"key":"204_CR7","doi-asserted-by":"crossref","unstructured":"Cai, L., Guo, C.: Contracting few edges to remove forbidden induced subgraphs. In: IPEC 2013, LNCS 8246, pp. 97\u2013109. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03898-8_10"},{"key":"204_CR8","unstructured":"Cai, L., Guo, C.: Contracting graphs to split graphs and threshold graphs. Manuscript, arXiv:1310.5786"},{"key":"204_CR9","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.tcs.2005.02.003","volume":"339","author":"Y Chen","year":"2005","unstructured":"Chen, Y., Flum, J., Grohe, M.: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339, 167\u2013199 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"204_CR10","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory (Electronic Edition). Springer, Berlin (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"204_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"204_CR12","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1016\/j.jcss.2010.12.001","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A generalization of Nemhauser and Trotter\u2019s local optimization theorem. J. Comput. Syst. Sci. 77, 1141\u20131158 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"204_CR13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval problems. Theor. Comput. Sci. 410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"204_CR14","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"204_CR15","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Co., New York (1979)"},{"key":"204_CR16","unstructured":"Golovach, P.A., van \u2019t Hof, P., Paulusma, D.: Obtaining planarity by contracting few edges. Theor. Comput. Sci. 476, 38\u201346 (2013)"},{"key":"204_CR17","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2013.02.030","volume":"481","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., Kami\u0144ski, M., Paulusma, D., Thilikos, D.M.: Increasing the minimum degree of a graph by contractions. Theor. Comput. Sci. 481, 74\u201384 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"22\u201324","key":"204_CR18","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1016\/j.ipl.2013.09.004","volume":"113","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Marx, D.: A faster FPT algorithm for bipartite contraction. Inf. Process. Lett. 113(22\u201324), 906\u2013912 (2013)","journal-title":"Inf. Process. Lett."},{"key":"204_CR19","doi-asserted-by":"crossref","unstructured":"Heggernes, P., van \u2019t Hof, P., L\u00e9v\u00eaque, B., Lokshtanov, D., Paul, C.: Contracting graphs to paths and trees. Algorithmica 68(1), 109\u2013132 (2014)","DOI":"10.1007\/s00453-012-9670-2"},{"key":"204_CR20","unstructured":"Heggernes, P., van \u2019t Hof, P., L\u00e9v\u00eaque, B., Lokshtanov, D., Paul, C.: Contracting chordal graphs and bipartite graphs to paths and trees. Discret. Appl. Math. 164(2), 444\u2013449 (2014)"},{"key":"204_CR21","unstructured":"Heggernes, P., van \u2019t Hof, P., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. SIAM J. Discret. Math. 27(4), 2143\u20132156 (2013)"},{"key":"204_CR22","doi-asserted-by":"crossref","first-page":"6340","DOI":"10.1016\/j.tcs.2011.07.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Kaminski, M., Paulusma, D., Thilikos, D.M.: Parameterizing cut sets in a graph by the number of their components. Theor. Comput. Sci. 412, 6340\u20136350 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"204_CR23","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20, 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"204_CR24","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: On the hardness of eliminating small induced subgraphs by contracting edges. In: IPEC 2013, LNCS 8246, pp. 243\u2013254. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03898-8_21"},{"issue":"4","key":"204_CR25","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"204_CR26","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/2500119","volume":"9","author":"D Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"34\u201336","key":"204_CR27","doi-asserted-by":"crossref","first-page":"3181","DOI":"10.1016\/j.tcs.2010.05.015","volume":"411","author":"L Mathieson","year":"2010","unstructured":"Mathieson, L.: The parameterized complexity of editing graphs for bounded degeneracy. Theor. Comput. Sci. 411(34\u201336), 3181\u20133187 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"204_CR28","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.jcss.2011.02.001","volume":"78","author":"L Mathieson","year":"2012","unstructured":"Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: a parameterized approach. J. Comput. Syst. Sci. 78, 179\u2013191 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"204_CR29","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7, 181\u2013190 (2009)","journal-title":"J. Discret. Algorithms"},{"key":"204_CR30","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"204_CR31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.dam.2005.02.029","volume":"152","author":"N Nishimura","year":"2005","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover. Discret. Appl. Math. 152, 229\u2013245 (2005)","journal-title":"Discret. Appl. Math."},{"key":"204_CR32","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Nondeterministic polynomial optimization problems and their approximations. Theor. Comput. Sci. 15, 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"204_CR33","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67, 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"204_CR34","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A $$4k^2$$ 4 k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","DOI":"10.1145\/1721837.1721848"},{"issue":"2","key":"204_CR35","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-014-0204-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-014-0204-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-014-0204-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T13:47:19Z","timestamp":1565704039000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-014-0204-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,3]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["204"],"URL":"https:\/\/doi.org\/10.1007\/s00236-014-0204-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,3]]}}}