{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T19:28:44Z","timestamp":1778354924419,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00453-019-00617-1","type":"journal-article","created":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T05:03:01Z","timestamp":1565931781000},"page":"853-880","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["On the Relation of Strong Triadic Closure and Cluster\u00a0Deletion"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6789-2918","authenticated-orcid":false,"given":"Niels","family":"Gr\u00fcttemeier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,16]]},"reference":[{"issue":"14","key":"617_CR1","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/j.ipl.2011.05.003","volume":"111","author":"S B\u00f6cker","year":"2011","unstructured":"B\u00f6cker, S., Damaschke, P.: Even faster parameterized cluster deletion and cluster editing. Inf. Process. Lett. 111(14), 717\u2013721 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"617_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"35","key":"617_CR3","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"617_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, vol. 3. SIAM, New Delhi (1999)"},{"key":"617_CR5","first-page":"99","volume-title":"Lecture Notes in Computer Science","author":"Laurent Bulteau","year":"2019","unstructured":"Bulteau, L., Gr\u00fcttemeier, N., Komusiewicz, C., Sorge, M.: Your rugby mates don\u2019t need to know your colleagues: triadic closure with edge colors. In: Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC\u201919). Lecture Notes in Computer Science, vol. 11485, pp. 99\u2013111. Springer, Berlin (2019)"},{"key":"617_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"617_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"issue":"23","key":"617_CR8","doi-asserted-by":"publisher","first-page":"2763","DOI":"10.1016\/j.disc.2013.08.017","volume":"313","author":"Y Gao","year":"2013","unstructured":"Gao, Y., Hare, D.R., Nastos, J.: The cluster deletion problem for cographs. Discrete Math. 313(23), 2763\u20132771 (2013)","journal-title":"Discrete Math."},{"key":"617_CR9","unstructured":"Golovach, P.A., Heggernes, P., Konstantinidis, A.L., Lima, P.T., Papadopoulos, C.: Parameterized aspects of strong subgraph closure. In: Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT\u201918). Leibniz International Proceedings in Informatics (LIPIcs), vol. 101, pp. 23:1\u201323:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"617_CR10","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1086\/225469","volume":"78","author":"MS Granovetter","year":"1973","unstructured":"Granovetter, M.S.: The strength of weak ties. Am. J. Sociol. 78, 1360\u20131380 (1973)","journal-title":"Am. J. Sociol."},{"key":"617_CR11","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-030-00256-5_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Niels Gr\u00fcttemeier","year":"2018","unstructured":"Gr\u00fcttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. In: Proceedings of the 44th International Workshop Graph-Theoretic Concepts in Computer Science (WG\u201918). Lecture Notes in Computer Science, vol. 11159, pp. 239\u2013251. Springer, Berlin (2018)"},{"issue":"8\u201310","key":"617_CR12","doi-asserted-by":"publisher","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":"617_CR13","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"617_CR14","first-page":"52","volume-title":"Lecture Notes in Computer Science","author":"Wen-Lian Hsu","year":"1991","unstructured":"Hsu, W.-L., Ma, T.-H.: Substitution decomposition on chordal graphs and applications. In: Proceedings of the 2nd international symposium on algorithms (ISA\u201991). Lecture Notes in Computer Science, vol. 557, pp. 52\u201360. Springer, Berlin (1991)"},{"issue":"15","key":"617_CR15","doi-asserted-by":"publisher","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","volume":"160","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math. 160(15), 2259\u20132270 (2012)","journal-title":"Discrete Appl. Math."},{"key":"617_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.tcs.2018.05.012","volume":"740","author":"AL Konstantinidis","year":"2018","unstructured":"Konstantinidis, A.L., Nikolopoulos, S.D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. Theor. Comput. Sci. 740, 76\u201384 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"617_CR17","unstructured":"Konstantinidis, A.L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. In: Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol.\u00a092, pp. 53:1\u201353:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"1\u20133","key":"617_CR18","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0012-365X(95)00109-A","volume":"159","author":"VB Le","year":"1996","unstructured":"Le, V.B.: Gallai graphs and anti-gallai graphs. Discrete Math. 159(1\u20133), 179\u2013189 (1996)","journal-title":"Discrete Math."},{"key":"617_CR19","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $${O(\\sqrt{|V|}|E|)}$$ algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS\u201980), pp. 17\u201327. IEEE Computer Society, Washington (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"617_CR20","doi-asserted-by":"crossref","unstructured":"Natanzon, A.: Complexity and approximation of some graph modification problems. Master thesis, University of Tel-Aviv (1999)","DOI":"10.1007\/3-540-46784-X_8"},{"issue":"1","key":"617_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(88)90143-3","volume":"28","author":"S Olariu","year":"1988","unstructured":"Olariu, S.: Paw-free graphs. Inf. Process. Lett. 28(1), 53\u201354 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"617_CR22","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carol. 15(2), 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"617_CR23","first-page":"216","volume":"14","author":"E Prisner","year":"1993","unstructured":"Prisner, E.: Hereditary clique-helly graphs. J. Comb. Math. Comb. Comput. 14, 216\u2013220 (1993)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"1","key":"617_CR24","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00224-007-9032-7","volume":"44","author":"F Protti","year":"2009","unstructured":"Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst. 44(1), 91\u2013104 (2009)","journal-title":"Theory Comput. Syst."},{"key":"617_CR25","doi-asserted-by":"crossref","unstructured":"Rozenshtein, P., Tatti, N., Gionis, A.: Inferring the strength of social ties: a community-driven approach. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201917), pp. 1017\u20131025. ACM (2017)","DOI":"10.1145\/3097983.3098199"},{"issue":"1","key":"617_CR26","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalite maximum dans un graphe sans etoile. Discrete Math. 29(1), 53\u201376 (1980)","journal-title":"Discrete Math."},{"issue":"1\u20132","key":"617_CR27","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 Appl. Math. 144(1\u20132), 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"617_CR28","doi-asserted-by":"crossref","unstructured":"Sintos, S., Tsaparas, P.: Using strong triadic closure to characterize ties in social networks. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201914), pp. 1466\u20131475. ACM, New York, NY (2014)","DOI":"10.1145\/2623330.2623664"},{"issue":"2","key":"617_CR29","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0095-8956(91)90078-X","volume":"53","author":"L Sun","year":"1991","unstructured":"Sun, L.: Two classes of perfect graphs. J. Comb. Theory Ser. B 53(2), 273\u2013292 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"617_CR30","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Tsidulko, O.Yu., Zschoche, P.: Fixed-parameter algorithms for maximum-profit facility location under matroid constraints. In: Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC\u201919), Lecture Notes in Computer Science, vol. 11485, pp. 62\u201374. Springer, Berlin (2019)","DOI":"10.1007\/978-3-030-17402-6_6"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00617-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00617-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00617-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T23:29:43Z","timestamp":1597447783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00617-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,16]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["617"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00617-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,16]]},"assertion":[{"value":"29 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}