{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:23Z","timestamp":1771036343084,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T00:00:00Z","timestamp":1674172800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T00:00:00Z","timestamp":1674172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FPTinP, NI 369\/19"],"award-info":[{"award-number":["FPTinP, NI 369\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MAGZ, KO 3669\/4-1"],"award-info":[{"award-number":["MAGZ, KO 3669\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EAGR, KO\u00a03669\/6-1"],"award-info":[{"award-number":["EAGR, KO\u00a03669\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,7]]},"abstract":"Abstract<\/jats:title>A graph\u00a0G<\/jats:italic> is weakly\u00a0$$\\gamma $$<\/jats:tex-math>\n \u03b3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-closed if every induced subgraph of\u00a0G<\/jats:italic> contains one vertex\u00a0v<\/jats:italic> such that for each non-neighbor\u00a0u<\/jats:italic> of\u00a0v<\/jats:italic> it holds that\u00a0$$ \\vert N(u)\\cap N(v) \\vert <\\gamma $$<\/jats:tex-math>\n \n |<\/mml:mo>\n N<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n \u2229<\/mml:mo>\n N<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n |<\/mml:mo>\n <<\/mml:mo>\n \u03b3<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The weak closure\u00a0$$\\gamma (G)$$<\/jats:tex-math>\n \n \u03b3<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a graph, recently introduced by Fox et al. (SIAM J Comput 49(2):448\u2013464, 2020), is the smallest number such that\u00a0G<\/jats:italic> is weakly\u00a0$$\\gamma $$<\/jats:tex-math>\n \u03b3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. (2020) on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s<\/jats:italic>-plexes, are fixed-parameter tractable with respect to\u00a0$$\\gamma (G)$$<\/jats:tex-math>\n \n \u03b3<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Moreover, we show that the problem of determining whether a weakly $$\\gamma $$<\/jats:tex-math>\n \u03b3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-closed graph\u00a0G<\/jats:italic> has a subgraph on at least\u00a0k<\/jats:italic> vertices that belongs to a graph class\u00a0$$\\mathcal {G}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> which is closed under taking subgraphs admits a kernel with at most\u00a0$$\\gamma k^2$$<\/jats:tex-math>\n \n \u03b3<\/mml:mi>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set<\/jats:sc> and Dominating Clique<\/jats:sc> when parameterized by\u00a0$$\\gamma +k$$<\/jats:tex-math>\n \n \u03b3<\/mml:mi>\n +<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where\u00a0k<\/jats:italic> is the solution size. Furthermore, we show that Independent Dominating Set<\/jats:sc> does not admit a polynomial kernel for constant\u00a0$$\\gamma $$<\/jats:tex-math>\n \u03b3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> under standard assumptions.<\/jats:p>","DOI":"10.1007\/s00453-022-01090-z","type":"journal-article","created":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T05:32:10Z","timestamp":1674279130000},"page":"2156-2187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing Dense and Sparse Subgraphs of Weakly Closed Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8684-0611","authenticated-orcid":false,"given":"Tomohiro","family":"Koana","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4034-525X","authenticated-orcid":false,"given":"Frank","family":"Sommer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,20]]},"reference":[{"issue":"4","key":"1090_CR1","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544\u2013556 (2009)","journal-title":"Algorithmica"},{"key":"1090_CR2","unstructured":"Behera, B., Husi\u0107, E., Jain, S., Roughgarden, T., Seshadhri, C.: FPT algorithms for finding near-cliques in $$c$$-closed graphs. In: Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS\u00a0\u201922), volume 215 of LIPIcs, pp. 17:1\u201317:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1090_CR3","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BF00191941","volume":"25","author":"A Blokhuis","year":"1988","unstructured":"Blokhuis, A., Brouwer, A.E.: Geodetic graphs of diameter two. Geom. Dedicata. 25, 527\u2013533 (1988)","journal-title":"Geom. Dedicata."},{"issue":"8","key":"1090_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(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1090_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(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"1090_CR6","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.dam.2016.09.040","volume":"217","author":"E Camby","year":"2017","unstructured":"Camby, E., Plein, F.: A note on an induced subgraph characterization of domination perfect graphs. Discrete Appl. Math. 217, 711\u2013717 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"9","key":"1090_CR7","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00607-012-0263-3","volume":"95","author":"M-S Chang","year":"2013","unstructured":"Chang, M.-S., Hung, L.-J., Lin, C.-R., Su, P.-C.: Finding large $$k$$-clubs in undirected graphs. Computing 95(9), 739\u2013758 (2013)","journal-title":"Computing"},{"issue":"1","key":"1090_CR8","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"1090_CR9","doi-asserted-by":"crossref","unstructured":"Conte, A., Firmani, D., Mordente, C., Patrignani, M., Torlone, R.: Fast enumeration of large $$k$$-plexes. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u00a0\u201917), pp. 115\u2013124. ACM (2017)","DOI":"10.1145\/3097983.3098031"},{"key":"1090_CR10","doi-asserted-by":"crossref","unstructured":"Conte, A., De Matteis, T., De Sensi, D., Grossi, R., Marino, A., Versari, L.: D2K: scalable community detection in massive networks via small-diameter $$k$$-plexes. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u00a0\u201918), pp. 1272\u20131281. ACM (2018)","DOI":"10.1145\/3219819.3220093"},{"issue":"8\u20139","key":"1090_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.ipl.2012.01.010","volume":"112","author":"J-F Couturier","year":"2012","unstructured":"Couturier, J.-F., Kratsch, D.: Bicolored independent sets and bicliques. Inf. Process. Lett. 112(8\u20139), 329\u2013334 (2012)","journal-title":"Inf. Process. Lett."},{"key":"1090_CR12","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)"},{"issue":"3","key":"1090_CR13","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/3108239","volume":"13","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Grandoni, F., Hermelin, D.: Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms 13(3), 43:1-43:22, (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"50","key":"1090_CR14","doi-asserted-by":"publisher","first-page":"6982","DOI":"10.1016\/j.tcs.2011.09.010","volume":"412","author":"M Cygan","year":"2011","unstructured":"Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50), 6982\u20137000 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"1090_CR15","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":"4","key":"1090_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0190(94)90121-X","volume":"51","author":"D Eppstein","year":"1994","unstructured":"Eppstein, D.: Arboricity and bipartite subgraph listing algorithms. Inf. Process. Lett. 51(4), 207\u2013211 (1994)","journal-title":"Inf. Process. Lett."},{"key":"1090_CR17","doi-asserted-by":"publisher","first-page":"3.1","DOI":"10.1145\/2543629","volume":"18","author":"D Eppstein","year":"2013","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithm. 18, 3.1-3.21 (2013)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"2","key":"1090_CR18","doi-asserted-by":"publisher","first-page":"543","DOI":"10.7155\/jgaa.00273","volume":"16","author":"D Eppstein","year":"2012","unstructured":"Eppstein, D., Spiro, E.S.: The $$h$$-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl. 16(2), 543\u2013567 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"1090_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.tcs.2017.09.027","volume":"734","author":"Q Feng","year":"2018","unstructured":"Feng, Q., Li, S., Zhou, Z., Wang, J.: Parameterized algorithms for edge biclique and related problems. Theor. Comput. Sci. 734, 105\u2013118 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1090_CR20","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/18M1210459","volume":"49","author":"J Fox","year":"2020","unstructured":"Fox, J., Roughgarden, T., Seshadhri, C., Wei, F., Wein, N.: Finding cliques in social networks: a new distribution-free model. SIAM J. Comput. 49(2), 448\u2013464 (2020)","journal-title":"SIAM J. Comput."},{"key":"1090_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"3","key":"1090_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified np-complete graph problems. Theoret. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"3\u20134","key":"1090_CR23","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s00453-010-9474-1","volume":"62","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. Algorithmica 62(3\u20134), 637\u2013658 (2012)","journal-title":"Algorithmica"},{"key":"1090_CR24","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Proceedings of the 34th International Workshop Graph-Theoretic Concepts in Computer Science (WG\u00a0\u201908), volume 5344 of Lecture Notes in Computer Science, pp. 195\u2013205 (2008)","DOI":"10.1007\/978-3-540-92248-3_18"},{"issue":"3","key":"1090_CR25","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3051095","volume":"64","author":"M Grohe","year":"2017","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM 64(3), 17:1-17:32 (2017)","journal-title":"J. ACM"},{"key":"1090_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.dam.2014.11.026","volume":"185","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Komusiewicz, C., Nichterlein, A., Such\u00fd, O.: On structural parameterizations for the 2-club problem. Discret. Appl. Math. 185, 79\u201392 (2015)","journal-title":"Discret. Appl. Math."},{"key":"1090_CR27","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/j.dam.2020.04.034","volume":"303","author":"D Hermelin","year":"2021","unstructured":"Hermelin, D., Manoussakis, G.: Efficient enumeration of maximal induced bicliques. Discrete Appl. Math. 303, 253\u2013261 (2021)","journal-title":"Discrete Appl. Math."},{"key":"1090_CR28","unstructured":"Kanesh, L., Madathil, J., Roy, S., Sahu, A., Saurabh, S.: Further exploiting $$c$$-closure for FPT algorithms and kernels for domination problems. In: Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS\u00a0\u201922), volume 219 of LIPIcs, pp. 39:1\u201339:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"2","key":"1090_CR29","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(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"1090_CR30","unstructured":"Koana, T., Komusiewicz, C., Nichterlein, A., Sommer, F.: Covering many (or few) edges with $$k$$ vertices in sparse graphs. In: Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS\u00a0\u201922), volume 219 of LIPIcs, pp. 42:1\u201342:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1090_CR31","unstructured":"Koana, T., Komusiewicz, C., Sommer, F.: Essentially tight kernels for (weakly) closed graphs. In: Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC\u00a0\u201921), volume 212 of LIPIcs, pp. 35:1\u201335:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"4","key":"1090_CR32","doi-asserted-by":"publisher","first-page":"2798","DOI":"10.1137\/21M1449476","volume":"36","author":"T Koana","year":"2022","unstructured":"Koana, T., Komusiewicz, C., Sommer, F.: Exploiting $$c$$-closure in kernelization algorithms for graph problems. SIAM J. Discrete Math. 36(4), 2798\u20132821 (2022)","journal-title":"SIAM J. Discrete Math."},{"key":"1090_CR33","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.dam.2021.06.019","volume":"302","author":"T Koana","year":"2021","unstructured":"Koana, T., Nichterlein, A.: Detecting and enumerating small induced subgraphs in $$c$$-closed graphs. Discrete Appl. Math. 302, 198\u2013207 (2021)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1090_CR34","doi-asserted-by":"publisher","first-page":"21","DOI":"10.3390\/a9010021","volume":"9","author":"C Komusiewicz","year":"2016","unstructured":"Komusiewicz, C.: Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1), 21 (2016)","journal-title":"Algorithms"},{"issue":"38\u201340","key":"1090_CR35","doi-asserted-by":"publisher","first-page":"3640","DOI":"10.1016\/j.tcs.2009.04.021","volume":"410","author":"C Komusiewicz","year":"2009","unstructured":"Komusiewicz, C., H\u00fcffner, F., Moser, H., Niedermeier, R.: Isolation concepts for efficiently enumerating dense subgraphs. Theor. Comput. Sci. 410(38\u201340), 3640\u20133654 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"1090_CR36","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.dam.2015.04.029","volume":"193","author":"C Komusiewicz","year":"2015","unstructured":"Komusiewicz, C., Sorge, M.: An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems. Discret. Appl. Math. 193, 145\u2013161 (2015)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"1090_CR37","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/3212622","volume":"65","author":"B Lin","year":"2018","unstructured":"Lin, B.: The parameterized complexity of the k-biclique problem. J. ACM 65(5), 34:1-34:23 (2018)","journal-title":"J. ACM"},{"key":"1090_CR38","unstructured":"Lokshtanov, D., Surianarayanan, V.: Dominating set in weakly closed graphs is fixed parameter tractable. In: Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u00a0\u201921), volume 213 of LIPIcs, pp. 29:1\u201329:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"1","key":"1090_CR39","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1090_CR40","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3(1), 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"issue":"3","key":"1090_CR41","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131(3), 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1090_CR42","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2390176.2390187","volume":"9","author":"G Philip","year":"2012","unstructured":"Philip, G., Raman, V.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 11:1-11:23 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1090_CR43","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"issue":"5","key":"1090_CR44","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","volume":"6","author":"A Sch\u00e4fer","year":"2012","unstructured":"Sch\u00e4fer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5), 883\u2013891 (2012)","journal-title":"Optim. Lett."},{"issue":"6","key":"1090_CR45","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D Seese","year":"1996","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci. 6(6), 505\u2013526 (1996)","journal-title":"Math. Struct. Comput. Sci."},{"issue":"3","key":"1090_CR46","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1002\/jgt.3190200313","volume":"20","author":"IE Zverovich","year":"1995","unstructured":"Zverovich, I.E., Zverovich, V.E.: An induced subgraph characterization of domination perfect graphs. J. Graph Theory 20(3), 375\u2013395 (1995)","journal-title":"J. Graph Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01090-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01090-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01090-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T05:58:39Z","timestamp":1687499919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01090-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,20]]},"references-count":46,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1090"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01090-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,20]]},"assertion":[{"value":"18 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}