{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:34Z","timestamp":1759637794803},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_3","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T07:57:26Z","timestamp":1384847846000},"page":"16-27","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints"],"prefix":"10.1007","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","reference":[{"issue":"2","key":"3_CR1","doi-asserted-by":"publisher","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.\u00a026(2), 197\u2013208 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"A.E. Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. J. Graph Theory\u00a011, 71\u201379 (1987)","journal-title":"J. Graph Theory"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","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. The Computer Journal\u00a051(1), 102\u2013121 (2008)","journal-title":"The Computer Journal"},{"doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, Electronic Edition. Springer-Verlag (2005)","key":"3_CR4","DOI":"10.1007\/978-3-642-14279-6_7"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","key":"3_CR5","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval problems. Theor. Comp. Sci.\u00a0410, 53\u201361 (2009)","journal-title":"Theor. Comp. Sci."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2012.12.041","volume":"476","author":"P.A. Golovach","year":"2013","unstructured":"Golovach, P.A., van \u2019t Hof, P., Paulusma, D.: Obtaining planarity by contracting few edges. Theor. Comp. Sci.\u00a0476, 38\u201346 (2013)","journal-title":"Theor. Comp. Sci."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2013.02.030","volume":"481","author":"P.A. 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. Comp. Sci.\u00a0481, 74\u201384 (2013)","journal-title":"Theor. Comp. Sci."},{"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 (to appear) doi:10.1007\/s00453-012-9670-2","key":"3_CR9","DOI":"10.1007\/s00453-012-9670-2"},{"unstructured":"Heggernes, P., van \u2019t Hof, P., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. In: FSTTCS 2011, LIPIcs, vol. 13, pp. 217\u2013228 (2011)","key":"3_CR10"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comp. System Sci.\u00a020, 219\u2013230 (1980)","journal-title":"J. Comp. System Sci."},{"unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. In: ACM Trans. Algorithms (to appear), Manuscript available at \n                  \n                    http:\/\/www.cs.bme.hu\/~dmarx\/papers\/marx-tw-reduction-talg.pdf","key":"3_CR12"},{"key":"3_CR13","doi-asserted-by":"publisher","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.\u00a078, 179\u2013191 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR14","doi-asserted-by":"publisher","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. Discr. Algorithms\u00a07, 181\u2013190 (2009)","journal-title":"J. Discr. Algorithms"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput.\u00a010(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:05:19Z","timestamp":1558695919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}