{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:19Z","timestamp":1759638979330},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_35","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"411-423","source":"Crossref","is-referenced-by-count":12,"title":["On the Threshold of Intractability"],"prefix":"10.1007","author":[{"given":"P\u00e5l Gr\u00f8n\u00e5s","family":"Drange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus Sortland","family":"Dregi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Blair D.","family":"Sullivan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"35_CR1","volume-title":"Social network algorithmics","author":"U. Brandes","year":"2014","unstructured":"Brandes, U.: Social network algorithmics. ISAAC, Invited talk (2014)"},{"key":"35_CR2","volume-title":"A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes. A Survey. SIAM, Philadelphia (1999)"},{"issue":"13","key":"35_CR3","doi-asserted-by":"publisher","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P. Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Discrete Applied Mathematics\u00a0154(13), 1824\u20131844 (2006)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"35_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters\u00a058(4), 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Cao, Y., Marx, D.: Chordal editing is fixed-parameter tractable. In: STACS. LIPIcs, vol.\u00a025, pp. 214\u2013225 (2014)","key":"35_CR5","DOI":"10.1137\/1.9781611973402.9"},{"doi-asserted-by":"crossref","unstructured":"Dehne, F., Langston, M., Luo, X., Pitre, S., Shaw, P., Zhang, Y.: The cluster editing problem: Implementations and experiments. In: IPEC (2006)","key":"35_CR6","DOI":"10.1007\/11847250_2"},{"doi-asserted-by":"crossref","unstructured":"Drange, P.G., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Exploring subexponential parameterized complexity of completion problems. In: STACS (2014)","key":"35_CR7","DOI":"10.1145\/2799640"},{"unstructured":"Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: ESA (to appear, 2015)","key":"35_CR8"},{"doi-asserted-by":"crossref","unstructured":"Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D.: On the threshold of intractability. CoRR, abs\/1505.00612 (2015)","key":"35_CR9","DOI":"10.1007\/978-3-662-48350-3_35"},{"issue":"17","key":"35_CR10","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1016\/j.ipl.2009.05.006","volume":"109","author":"T. Feder","year":"2009","unstructured":"Feder, T., Mannila, H., Terzi, E.: Approximating the minimum chain completion problem. Information Processing Letters\u00a0109(17), 980\u2013985 (2009)","journal-title":"Information Processing Letters"},{"issue":"6","key":"35_CR11","doi-asserted-by":"publisher","first-page":"2197","DOI":"10.1137\/11085390X","volume":"42","author":"F.V. Fomin","year":"2013","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput.\u00a042(6), 2197\u20132216 (2013)","journal-title":"SIAM J. Comput."},{"key":"35_CR12","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"35_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/978-3-540-77120-3_79","volume-title":"Algorithms and Computation","author":"J. Guo","year":"2007","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: Split and related graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 915\u2013926. Springer, Heidelberg (2007)"},{"issue":"4","key":"35_CR14","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1109\/TST.2014.6867517","volume":"19","author":"Y. Liu","year":"2014","unstructured":"Liu, Y., Wang, J., Guo, J.: An overview of kernelization algorithms for graph modification problems. Tsinghua Science and Technology\u00a019(4), 346\u2013357 (2014)","journal-title":"Tsinghua Science and Technology"},{"key":"35_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.tcs.2011.11.040","volume":"461","author":"Y. Liu","year":"2012","unstructured":"Liu, Y., Wang, J., Guo, J., Chen, J.: Complexity and parameterized algorithms for cograph editing. TCS\u00a0461, 45\u201354 (2012)","journal-title":"TCS"},{"key":"35_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2015.01.049","volume":"573","author":"Y. Liu","year":"2015","unstructured":"Liu, Y., Wang, J., You, J., Chen, J., Cao, Y.: Edge deletion problems: Branching facilitated by modular decomposition. Theoretical Computer Science\u00a0573, 63\u201370 (2015)","journal-title":"Theoretical Computer Science"},{"unstructured":"Mahadev, N., Peled, U.: Threshold graphs and related topics, vol.\u00a056. Elsevier (1995)","key":"35_CR17"},{"unstructured":"Mancini, F.: Graph modification problems related to graph classes. PhD thesis, University of Bergen (2008)","key":"35_CR18"},{"issue":"3","key":"35_CR19","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.socnet.2013.05.001","volume":"35","author":"J. Nastos","year":"2013","unstructured":"Nastos, J., Gao, Y.: Familial groups in social networks. Social Networks\u00a035(3), 439\u2013450 (2013)","journal-title":"Social Networks"},{"doi-asserted-by":"crossref","unstructured":"Natanzon, A.: Complexity and approximation of some graph modification problems. PhD thesis, Tel Aviv University (1999)","key":"35_CR20","DOI":"10.1007\/3-540-46784-X_8"},{"issue":"1","key":"35_CR21","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A. Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Applied Mathematics\u00a0113(1), 109\u2013128 (2001)","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Schoch, D., Brandes, U.: Stars, neighborhood inclusion, and network centrality. In: SIAM Workshop on Network Science (2015)","key":"35_CR22"},{"issue":"1","key":"35_CR23","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R. Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Applied Mathematics\u00a0144(1), 173\u2013182 (2004)","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Sharan, R.: Graph modification problems and their applications to genomic research. PhD thesis, Tel-Aviv University (2002)","key":"35_CR24"},{"issue":"1","key":"35_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic and Discrete Methods\u00a02(1), 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T04:43:16Z","timestamp":1653108196000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}