{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:10Z","timestamp":1759637770508},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_1","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"3-15","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics"],"prefix":"10.1007","author":[{"given":"Christian","family":"Komusiewicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/j.tcs.2015.06.053","volume":"607","author":"FN Abu-Khzam","year":"2015","unstructured":"Abu-Khzam, F.N., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: On the parameterized complexity of dynamic problems. Theoret. Comput. Sci. 607, 426\u2013434 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.tcs.2016.02.004","volume":"622","author":"C Bazgan","year":"2016","unstructured":"Bazgan, C., Bredereck, R., Hartung, S., Nichterlein, A., Woeginger, G.J.: Finding large degree-anonymous subgraphs is hard. Theoret. Comput. Sci. 622, 90\u2013110 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"3\u20134","key":"1_CR3","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1007\/s00453-011-9492-7","volume":"62","author":"R Bevern van","year":"2012","unstructured":"van Bevern, R., Moser, H., Niedermeier, R.: Approximation and tidying - a problem kernel for $$s$$ -plex cluster vertex deletion. Algorithmica 62(3\u20134), 930\u2013950 (2012)","journal-title":"Algorithmica"},{"issue":"7\u20139","key":"1_CR4","doi-asserted-by":"crossref","first-page":"1202","DOI":"10.1016\/j.tcs.2009.12.016","volume":"411","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Fellows, M.R., Heggernes, P., Mancini, F., Papadopoulos, C., Rosamond, F.A.: Clustering with partial information. Theoret. Comput. Sci. 411(7\u20139), 1202\u20131211 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1_CR5","first-page":"38","volume":"4","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Heggernes, P., Lokshtanov, D.: Graph modification problems (Dagstuhl seminar 14071). Dagstuhl Rep. 4(2), 38\u201359 (2014)","journal-title":"Dagstuhl Rep."},{"issue":"4","key":"1_CR6","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1109\/TST.2014.6867518","volume":"19","author":"R Bredereck","year":"2014","unstructured":"Bredereck, R., Chen, J., Faliszewski, P., Guo, J., Niedermeier, R., Woeginger, G.J.: Parameterized algorithmics for computational social choice: nine research challenges. Tsinghua Sci. Technol. 19(4), 358\u2013373 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tcs.2015.07.004","volume":"607","author":"R Bredereck","year":"2015","unstructured":"Bredereck, R., Froese, V., Hartung, S., Nichterlein, A., Niedermeier, R., Talmon, N.: The complexity of degree anonymization by vertex addition. Theoret. Comput. Sci. 607, 16\u201334 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR8","first-page":"31","volume":"114","author":"L Bulteau","year":"2014","unstructured":"Bulteau, L., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R.: Multivariate algorithmics for NP-hard string problems. Bull. EATCS 114, 31\u201373 (2014)","journal-title":"Bull. EATCS"},{"issue":"4","key":"1_CR9","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1137\/0114065","volume":"14","author":"G Chartrand","year":"1966","unstructured":"Chartrand, G.: A graph-theoretic approach to a communications problem. SIAM J. Appl. Math. 14(4), 778\u2013781 (1966)","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-1-4419-6515-8_14","volume-title":"Link Mining: Models, Algorithms, and Applications","author":"KL Clarkson","year":"2010","unstructured":"Clarkson, K.L., Liu, K., Terzi, E.: Towards identity anonymization in social networks. In: Yu, P.S., Han, J., Faloutsos, C. (eds.) Link Mining: Models, Algorithms, and Applications, pp. 359\u2013385. Springer, New York (2010)"},{"issue":"4","key":"1_CR11","doi-asserted-by":"crossref","first-page":"557","DOI":"10.7155\/jgaa.00337","volume":"18","author":"P Damaschke","year":"2014","unstructured":"Damaschke, P., Mogren, O.: Editing simple graphs. J. Graph Algorithms Appl. 18(4), 557\u2013576 (2014)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"1_CR12","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1109\/TST.2014.6867515","volume":"19","author":"RG Downey","year":"2014","unstructured":"Downey, R.G., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: Dynamic dominating set and turbo-charging greedy heuristics. Tsinghua Sci. Technol. 19(4), 329\u2013337 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.tcs.2014.05.002","volume":"542","author":"M D\u00f6rnfelder","year":"2014","unstructured":"D\u00f6rnfelder, M., Guo, J., Komusiewicz, C., Weller, M.: On the parameterized complexity of consensus clustering. Theoret. Comput. Sci. 542, 71\u201382 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1_CR14","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/j.jcss.2011.10.003","volume":"78","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707\u2013719 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.disopt.2010.09.006","volume":"8","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optim. 8(1), 2\u201317 (2011)","journal-title":"Discrete Optim."},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Fast local search algorithm for weighted feedback arc set in tournaments. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, (AAAI 2010), pp. 65\u201370 (2010)","DOI":"10.1609\/aaai.v24i1.7557"},{"issue":"6","key":"1_CR17","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1016\/j.jcss.2016.03.009","volume":"82","author":"V Froese","year":"2016","unstructured":"Froese, V., Nichterlein, A., Niedermeier, R.: Win-win kernelization for degree sequence completion problems. J. Comput. Syst. Sci. 82(6), 1100\u20131111 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1_CR18","first-page":"14:1","volume":"42","author":"BCM Fung","year":"2010","unstructured":"Fung, B.C.M., Wang, K., Chen, R., Yu, P.S.: Privacy-preserving data publishing: a survey of recent developments. ACM Comput. Surv. 42(4), 14:1\u201314:53 (2010)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"1_CR19","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theor. Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theor. Comput. Syst."},{"issue":"4","key":"1_CR20","doi-asserted-by":"crossref","first-page":"1662","DOI":"10.1137\/090767285","volume":"24","author":"J Guo","year":"2010","unstructured":"Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: A more relaxed model for graph-based data clustering: $$s$$ -plex cluster editing. SIAM J. Discrete Math. 24(4), 1662\u20131683 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/978-3-319-07959-2_32","volume-title":"Experimental Algorithms","author":"S Hartung","year":"2014","unstructured":"Hartung, S., Hoffmann, C., Nichterlein, A.: Improved upper and lower bound heuristics for degree anonymization in social networks. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 376\u2013387. Springer, Heidelberg (2014)"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/978-3-319-19084-6_5","volume-title":"Learning and Intelligent Optimization","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Hoos, H.H.: Programming by optimisation meets parameterised algorithmics: a case study for cluster editing. In: Jourdan, L., Dhaenens, C., Marmion, M.-E. (eds.) LION 9 2015. LNCS, vol. 8994, pp. 43\u201358. Springer, Heidelberg (2015)"},{"key":"1_CR23","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.ic.2014.12.017","volume":"243","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Nichterlein, A., Niedermeier, R., Such\u00fd, O.: A refined complexity analysis of degree anonymization in graphs. Inf. Comput. 243, 249\u2013262 (2015)","journal-title":"Inf. Comput."},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2012.12.049","volume":"494","author":"S Hartung","year":"2013","unstructured":"Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theoret. Comput. Sci. 494, 86\u201398 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-319-17142-5_23","volume-title":"Theory and Applications of Models of Computation","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Talmon, N.: The complexity of degree anonymization by graph contractions. In: Jain, R., Jain, S., Stephan, F. (eds.) TAMC 2015. LNCS, vol. 9076, pp. 260\u2013271. Springer, Heidelberg (2015)"},{"issue":"4\u20136","key":"1_CR26","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0020-0190(00)00142-3","volume":"76","author":"E Hartuv","year":"2000","unstructured":"Hartuv, E., Shamir, R.: A clustering algorithm based on graph connectivity. Inf. Process. Lett. 76(4\u20136), 175\u2013181 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1_CR27","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/2076450.2076469","volume":"55","author":"HH Hoos","year":"2012","unstructured":"Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70\u201380 (2012)","journal-title":"Commun. ACM"},{"issue":"3","key":"1_CR28","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/TCBB.2013.177","volume":"11","author":"F H\u00fcffner","year":"2014","unstructured":"H\u00fcffner, F., Komusiewicz, C., Liebtrau, A., Niedermeier, R.: Partitioning biological networks into highly connected clusters with maximum edge coverage. IEEE\/ACM Trans. Comput. Biol. Bioinf. 11(3), 455\u2013467 (2014)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"1","key":"1_CR29","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theor. Comput. Syst. 47(1), 196\u2013217 (2010)","journal-title":"Theor. Comput. Syst."},{"issue":"4","key":"1_CR30","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.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1_CR31","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jcss.2010.06.009","volume":"77","author":"RM Karp","year":"2011","unstructured":"Karp, R.M.: Heuristic algorithms in computational molecular biology. J. Comput. Syst. Sci. 77(1), 122\u2013128 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-29700-7_22","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"H Liu","year":"2012","unstructured":"Liu, H., Zhang, P., Zhu, D.: On editing graphs into 2-club clusters. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 235\u2013246. Springer, Heidelberg (2012)"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2008), pp. 93\u2013106 (2008)","DOI":"10.1145\/1376616.1376629"},{"issue":"4","key":"1_CR34","doi-asserted-by":"crossref","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 Sci. Technol. 19(4), 346\u2013357 (2014)","journal-title":"Tsinghua Sci. Technol."},{"issue":"2","key":"1_CR35","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"1_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-642-32600-4_21","volume-title":"Database and Expert Systems Applications","author":"X Lu","year":"2012","unstructured":"Lu, X., Song, Y., Bressan, S.: Fast identity anonymization on graphs. In: Liddle, S.W., Schewe, K.-D., Tjoa, A.M., Zhou, X. (eds.) DEXA 2012, Part I. LNCS, vol. 7446, pp. 281\u2013295. Springer, Heidelberg (2012)"},{"issue":"2","key":"1_CR37","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"1_CR38","volume-title":"Algorithms and Data Structures: The Basic Toolbox","author":"K Mehlhorn","year":"2008","unstructured":"Mehlhorn, K., Sanders, P.: Algorithms and Data Structures: The Basic Toolbox. Springer, Heidelberg (2008)"},{"issue":"1","key":"1_CR39","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"GL Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48\u201361 (1974)","journal-title":"Math. Program."},{"key":"1_CR40","unstructured":"Nichterlein, A.: Degree-Constrained Editing of Small-Degree Graphs. Ph.D. thesis, TU Berlin (2015)"},{"key":"1_CR41","series-title":"Advances in Database Systems","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/978-1-4419-6045-0_14","volume-title":"Managing and Mining Graph Data","author":"X Wu","year":"2010","unstructured":"Wu, X., Ying, X., Liu, K., Chen, L.: A survey of privacy-preservation of graphs and social networks. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data. Advances in Database Systems, vol. 40, pp. 421\u2013453. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T10:00:48Z","timestamp":1692439248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}