{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:19:52Z","timestamp":1773886792829,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,1,12]],"date-time":"2011-01-12T00:00:00Z","timestamp":1294790400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-011-9487-4","type":"journal-article","created":{"date-parts":[[2011,1,11]],"date-time":"2011-01-11T19:36:01Z","timestamp":1294774561000},"page":"949-970","source":"Crossref","is-referenced-by-count":15,"title":["Editing Graphs into Disjoint Unions of Dense Clusters"],"prefix":"10.1007","volume":"61","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Uhlmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,1,12]]},"reference":[{"key":"9487_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1007\/3-540-45995-2_51","volume-title":"Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN \u201902)","author":"J. Abello","year":"2002","unstructured":"Abello, J., Resende, M.G.C., Sudarsky, S.: Massive quasi-clique detection. In: Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN \u201902). Lecture Notes in Computer Science, vol. 2286, pp. 598\u2013612. Springer, Berlin (2002)"},{"issue":"5","key":"9487_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N. Ailon","year":"2008","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), 23 (2008), 27\u00a0pp.","journal-title":"J. ACM"},{"issue":"1\u20133","key":"9487_CR3","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1\u20133), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"issue":"52","key":"9487_CR4","doi-asserted-by":"crossref","first-page":"5467","DOI":"10.1016\/j.tcs.2009.05.006","volume":"410","author":"S. B\u00f6cker","year":"2009","unstructured":"B\u00f6cker, S., Briesemeister, S., Bui, Q.B.A., Tru\u00df, A.: Going weighted: parameterized algorithms for cluster editing. Theor. Comput. Sci. 410(52), 5467\u20135480 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9487_CR5","doi-asserted-by":"crossref","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. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9487_CR6","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC \u201910)","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J.: Weighted cluster editing: kernelization based on edge-cuts. In: Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC \u201910). Lecture Notes in Computer Science. Springer, Berlin (2010)"},{"key":"9487_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-3-642-14031-0_49","volume-title":"Proceedings of the 16th Annual International Conference on Computing and Combinatorics (COCOON \u201910)","author":"J. Chen","year":"2010","unstructured":"Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. In: Proceedings of the 16th Annual International Conference on Computing and Combinatorics (COCOON \u201910). Lecture Notes in Computer Science, vol. 6196, pp. 459\u2013468. Springer, Berlin (2010)"},{"issue":"3","key":"9487_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1038\/ng1518","volume":"37","author":"E.J. Chesler","year":"2005","unstructured":"Chesler, E.J., Lu, L., Shou, S., Qu, Y., Gu, J., Wang, J., Hsu, H.C., Mountz, J.D., Baldwin, N.E., Langston, M.A., Threadgill, D.W., Manly, K.F., Williams, R.W.: Complex trait analysis of gene expression uncovers polygenic and pleiotropic networks that modulate nervous system function. Nat. Genet. 37(3), 233\u2013242 (2005)","journal-title":"Nat. Genet."},{"key":"9487_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/11847250_2","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC \u201906)","author":"F.K.H.A. Dehne","year":"2006","unstructured":"Dehne, F.K.H.A., Langston, M.A., Luo, X., Pitre, S., Shaw, P., Zhang, Y.: The cluster editing problem: Implementations and experiments. In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC \u201906). Lecture Notes in Computer Science, vol. 4169, pp. 13\u201324. Springer, Berlin (2006)"},{"key":"9487_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9487_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/978-3-540-74240-1_27","volume-title":"Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT \u201907)","author":"M.R. Fellows","year":"2007","unstructured":"Fellows, M.R., Langston, M.A., Rosamond, F.A., Shaw, P.: Efficient parameterized preprocessing for Cluster Editing. In: Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT \u201907). Lecture Notes in Computer Science, vol. 4639, pp. 312\u2013321. Springer, Berlin (2007)"},{"issue":"1","key":"9487_CR12","doi-asserted-by":"crossref","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.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9487_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"4","key":"9487_CR14","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. Theory Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"key":"9487_CR15","first-page":"389","volume-title":"Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing","author":"D.L. Greenwell","year":"1973","unstructured":"Greenwell, D.L., Hemminger, R.L., Klerlein, J.B.: Forbidden subgraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 389\u2013394 (1973)"},{"issue":"8\u201310","key":"9487_CR16","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1016\/j.tcs.2008.10.021","volume":"410","author":"J. Guo","year":"2009","unstructured":"Guo, J.: A more effective linear kernelization for Cluster Editing. Theor. Comput. Sci. 410(8\u201310), 718\u2013726 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9487_CR17","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."},{"issue":"7","key":"9487_CR18","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1073\/pnas.48.7.1142","volume":"48","author":"F. Harary","year":"1962","unstructured":"Harary, F.: The maximum connectivity of a graph. Proc. Natl. Acad. Sci. USA 48(7), 1142\u20131146 (1962)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"9487_CR19","series-title":"Lecture Notes in Computer Science","first-page":"112","volume-title":"Network Analysis","author":"S. Kosub","year":"2004","unstructured":"Kosub, S.: Local density. In: Network Analysis. Lecture Notes in Computer Science, vol.\u00a03418, pp.\u00a0112\u2013142. Springer, Berlin (2004)"},{"issue":"3","key":"9487_CR20","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF00289116","volume":"23","author":"M. K\u0159iv\u00e1nek","year":"1986","unstructured":"K\u0159iv\u00e1nek, M., Mor\u00e1vek, J.: NP-hard problems in hierarchical-tree clustering. Acta Inform. 23(3), 311\u2013323 (1986)","journal-title":"Acta Inform."},{"key":"9487_CR21","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, London (2006)"},{"key":"9487_CR22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"S.B. Seidman","year":"1978","unstructured":"Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept. J. Math. Sociol. 6, 139\u2013154 (1978)","journal-title":"J. Math. Sociol."},{"issue":"1\u20132","key":"9487_CR23","doi-asserted-by":"crossref","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 Appl. Math. 144(1\u20132), 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"9487_CR24","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1093\/bioinformatics\/btl014","volume":"22","author":"H. Yu","year":"2006","unstructured":"Yu, H., Paccanaro, A., Trifonov, V., Gerstein, M.: Predicting interactions in protein networks by completing defective cliques. Bioinformatics 22(7), 823\u2013829 (2006)","journal-title":"Bioinformatics"},{"issue":"3","key":"9487_CR25","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1287\/moor.1090.0385","volume":"34","author":"A. Zuylen van","year":"2009","unstructured":"van Zuylen, A., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. Math. Oper. Res. 34(3), 594\u2013620 (2009)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9487-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9487-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9487-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:07Z","timestamp":1559137507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9487-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9487"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9487-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,12]]}}}