{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T09:04:36Z","timestamp":1768467876498,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T00:00:00Z","timestamp":1580860800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T00:00:00Z","timestamp":1580860800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["CLASSIS"],"award-info":[{"award-number":["CLASSIS"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003447","name":"State Scholarships Foundation","doi-asserted-by":"publisher","award":["MIS-5000432"],"award-info":[{"award-number":["MIS-5000432"]}],"id":[{"id":"10.13039\/501100003447","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00684-9","type":"journal-article","created":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T13:32:38Z","timestamp":1583501558000},"page":"2006-2038","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Aspects of Strong Subgraph Closure"],"prefix":"10.1007","volume":"82","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Athanasios L.","family":"Konstantinidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5556-2981","authenticated-orcid":false,"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,5]]},"reference":[{"key":"684_CR1","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-Hitting set. J. Comput. Syst. Sci. 76, 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"684_CR2","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61, 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"684_CR3","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Kleinberg, J.: Romantic partnerships and the dispersion of social ties: a network analysis of relationship status on facebook. In: CSCW 2014, pp.\u00a0831\u2013841 (2014)","DOI":"10.1145\/2531602.2531642"},{"key":"684_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"684_CR5","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, 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"684_CR6","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. Inf. Process. Lett. 58, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"684_CR7","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s00453-014-9937-x","volume":"71","author":"L Cai","year":"2015","unstructured":"Cai, L., Cai, Y.: Incompressibility of $$H$$-free edge modification problems. Algorithmica 71, 731\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"684_CR8","doi-asserted-by":"crossref","unstructured":"Cai, L., Chan, S., Chan, S.: Random separation: a new method for solving fixed-cardinality optimization problems. In: IWPEC 2006, pp.\u00a0239\u2013250 (2006)","DOI":"10.1007\/11847250_22"},{"key":"684_CR9","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/15M1032077","volume":"45","author":"R Chitnis","year":"2016","unstructured":"Chitnis, R., Cygan, M., Hajiaghayi, M., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput. 45, 1171\u20131229 (2016)","journal-title":"SIAM J. Comput."},{"key":"684_CR10","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":"684_CR11","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2012)","edition":"4"},{"key":"684_CR12","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11, 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"684_CR13","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"684_CR14","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","volume":"7","author":"ME Dyer","year":"1986","unstructured":"Dyer, M.E., Frieze, A.M.: Planar 3DM is NP-complete. J. Algorithms 7, 174\u2013184 (1986)","journal-title":"J. Algorithms"},{"key":"684_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, Crowds, and Markets: Reasoning About a Highly Connected World","author":"D Easley","year":"2010","unstructured":"Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)"},{"key":"684_CR16","unstructured":"Golovach, P.\u00a0A., Heggernes, P., Konstantinidis, A.\u00a0L., Lima, P.\u00a0T., Papadopoulos, C.: Parameterized aspects of strong subgraph closure. In: SWAT 2018, pp.\u00a023:1\u201323:13 (2018)"},{"key":"684_CR17","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics. Elsevier, Amsterdam (2004)"},{"key":"684_CR18","doi-asserted-by":"crossref","unstructured":"Gr\u00fcttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. In: WG 2018, volume 11159 of Lecture Notes in Computer Science, pp. 239\u2013251. Springer (2018)","DOI":"10.1007\/978-3-030-00256-5_20"},{"key":"684_CR19","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289, 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"684_CR20","volume-title":"Algorithm Design","author":"JM Kleinberg","year":"2006","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Algorithm Design. Addison-Wesley, Boston (2006)"},{"key":"684_CR21","doi-asserted-by":"crossref","unstructured":"Konstantinidis, A.\u00a0L., Nikolopoulos, S.\u00a0D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. In: COCOON 2017, pp.\u00a0346\u2013358 (2017)","DOI":"10.1007\/978-3-319-62389-4_29"},{"key":"684_CR22","unstructured":"Konstantinidis, A.\u00a0L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. In: ISAAC 2017, pp.\u00a053:1\u201353:12 (2017)"},{"key":"684_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.disopt.2013.02.001","volume":"10","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Wahlstrom, M.: Two edge modification problems without polynomial kernels. Discrete Optim. 10, 193\u2013199 (2013)","journal-title":"Discrete Optim."},{"key":"684_CR24","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.\u00a0V.: An $$O(\\sqrt{|V|} |E|)$$ algorithm for finding maximum matching in general graphs. In: FOCS 1980, pp.\u00a017\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"684_CR25","doi-asserted-by":"crossref","unstructured":"Sintos, S., Tsaparas, P.: Using strong triadic closure to characterize ties in social networks. In: KDD 2014, pp.\u00a01466\u20131475 (2014)","DOI":"10.1145\/2623330.2623664"},{"key":"684_CR26","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. 10, 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00684-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00684-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00684-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T00:14:38Z","timestamp":1612397678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00684-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,5]]},"references-count":26,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["684"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00684-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,5]]},"assertion":[{"value":"10 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}