{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:12Z","timestamp":1740107112542,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T00:00:00Z","timestamp":1659052800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T00:00:00Z","timestamp":1659052800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005874","name":"Universit\u00e0 degli Studi G. D'Annunzio Chieti Pescara","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005874","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,8]]},"abstract":"Abstract<\/jats:title>The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS is solvable in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. For any two graphs G<\/jats:italic> and H<\/jats:italic>, $$G+H$$<\/jats:tex-math>\n \n G<\/mml:mi>\n +<\/mml:mo>\n H<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the disjoint union of G<\/jats:italic> and H<\/jats:italic>. A $$lK_2$$<\/jats:tex-math>\n \n l<\/mml:mi>\n \n K<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the disjoint union of l<\/jats:italic> edges. A $$Y_{m,m}$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n \n m<\/mml:mi>\n ,<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the disjoint union of two stars of $$m+1$$<\/jats:tex-math>\n \n m<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices plus one vertex that is adjacent only to the centers of such stars. For any graph family $${{{\\mathcal {Y}}}}$$<\/jats:tex-math>\n Y<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the class of $${\\mathcal Y}$$<\/jats:tex-math>\n Y<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs is formed by graphs which are Y<\/jats:italic>-free for every $$Y \\in {{{\\mathcal {Y}}}}$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n \u2208<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and the class of $$lK_2+{{{\\mathcal {Y}}}}$$<\/jats:tex-math>\n \n l<\/mml:mi>\n \n K<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs is formed by graph which are $$lK_2+Y$$<\/jats:tex-math>\n \n l<\/mml:mi>\n \n K<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free for every $$Y \\in {\\mathcal Y}$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n \u2208<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.\u00a0The main result of this manuscript is the following: For any constant m<\/jats:italic> and for any graph family $${{{\\mathcal {Y}}}}$$<\/jats:tex-math>\n Y<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> which contains an induced subgraph of $$Y_{m,m}$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n \n m<\/mml:mi>\n ,<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, if WIS is solvable in polynomial time for $${{{\\mathcal {Y}}}}$$<\/jats:tex-math>\n Y<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs, then WIS is solvable in polynomial time for $$lK_2+{{{\\mathcal {Y}}}}$$<\/jats:tex-math>\n \n l<\/mml:mi>\n \n K<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs for any constant l<\/jats:italic>. That extends some known polynomial results, namely, when $${{{\\mathcal {Y}}}} = \\{Y\\}$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n Y<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and Y<\/jats:italic> is a fork or is a $$P_5$$<\/jats:tex-math>\n \n P<\/mml:mi>\n 5<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.\u00a0The proof of the main result is based on Farber\u2019s approach to prove that every $$2K_2$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n \n K<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graph has $$O(n^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> maximal independent sets (Farber in Discrete Math 73:249\u2013260, 1989), which directly leads to a polynomial time algorithm to solve WIS for $$2K_2$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n \n K<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs through a dynamic programming approach, and on some extensions of Farber\u2019s approach.<\/jats:p>","DOI":"10.1007\/s00373-022-02532-9","type":"journal-article","created":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T18:24:44Z","timestamp":1659119084000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["New Results on Independent Sets in Extensions of $$2K_2$$-free Graphs"],"prefix":"10.1007","volume":"38","author":[{"given":"Raffaele","family":"Mosca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,29]]},"reference":[{"key":"2532_CR1","first-page":"3","volume-title":"Combinatorial-algebraic Methods in Applied Mathematics","author":"VE Alekseev","year":"1983","unstructured":"Alekseev, V.E.: On the local restriction effect on the complexity of finding the graph independence number. In: Combinatorial-algebraic Methods in Applied Mathematics, pp. 3\u201313. Gorkiy University Press, Gorkiy (1983). (in Russian)"},{"key":"2532_CR2","first-page":"5","volume-title":"Combinatorial-algebraic Methods in Discrete Optimization","author":"VE Alekseev","year":"1991","unstructured":"Alekseev, V.E.: On the number of maximal independent sets in graphs from hereditary classes. In: Combinatorial-algebraic Methods in Discrete Optimization, pp. 5\u20138. Gorkiy University Press, Gorkiy (1991). (in Russian)"},{"key":"2532_CR3","doi-asserted-by":"crossref","unstructured":"Alekseev, V.E.: A polynomial algorithm for finding largest independent sets in graphs without forks, Discrete analysis and operations research ser. 1, 6 (1999) 3\u201319 (in Russian). Discrete Appl. Math. 135, 3\u201316 (2004)","DOI":"10.1016\/S0166-218X(02)00290-1"},{"key":"2532_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0166-218X(03)00387-1","volume":"132","author":"VE Alekseev","year":"2003","unstructured":"Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discret. Appl. Math. 132, 17\u201326 (2003)","journal-title":"Discret. Appl. Math."},{"key":"2532_CR5","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00453-018-0479-5","volume":"81","author":"G Bacs\u00f3","year":"2019","unstructured":"Bacs\u00f3, G., Lokshtanov, D., Marx, D., Pilipczuk, M., Tuza, Z., van Leeuwen, E.J.: Subexponential-time algorithms for maximum independent set in $$P_t$$-free and broom-free graphs. Algorithmica 81, 421\u2013438 (2019)","journal-title":"Algorithmica"},{"key":"2532_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl.","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl., vol. 3. SIAM, Philadelphia (1999)"},{"key":"2532_CR7","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1137\/090750822","volume":"24","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Lozin, V.V., Mosca, R.: Independent sets of maximum weight in apple-free graphs. SIAM J. Discrete Math. 24, 239\u2013254 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"2532_CR8","first-page":"848","volume":"5369","author":"A Brandst\u00e4dt","year":"2008","unstructured":"Brandst\u00e4dt, A., Klembt, T., Lozin, V.V., Mosca, R.: Independent sets of maximum weight in apple-free graphs, ISAAC 2008. LNCS 5369, 848\u2013858 (2008)","journal-title":"LNCS"},{"key":"2532_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.dam.2017.11.029","volume":"237","author":"A Brandst\u00e4dt","year":"2018","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent set for $$l$$claw-free graphs in polynomial time. Discret. Appl. Math. 237, 57\u201364 (2018)","journal-title":"Discret. Appl. Math."},{"key":"2532_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.dam.2016.06.016","volume":"231","author":"C Brause","year":"2017","unstructured":"Brause, C.: A subexponential-time algorithm for the Maximum Independent Set Problem in $$P_t$$-free graphs. Discret. Appl. Math. 231, 113\u2013118 (2017)","journal-title":"Discret. Appl. Math."},{"key":"2532_CR11","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14, 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"2532_CR12","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1007\/s00373-015-1660-0","volume":"32","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Lozin, V.V., de Werra, D., Zamaraev, V.: Combinatorics and algorithms for augmenting graphs. Graphs Comb. 32, 1339\u20131352 (2016)","journal-title":"Graphs Comb."},{"key":"2532_CR13","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an O($$n^3$$)-algorithm for the weighted stable set problem. In: SODA, pp. 630\u2013646 (2011)","DOI":"10.1137\/1.9781611973082.49"},{"key":"2532_CR14","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0012-365X(89)90268-9","volume":"73","author":"M Farber","year":"1989","unstructured":"Farber, M.: On diameters and radii of bridged graphs. Discrete Math. 73, 249\u2013260 (1989)","journal-title":"Discrete Math."},{"key":"2532_CR15","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/net.3230230308","volume":"23","author":"M Farber","year":"1993","unstructured":"Farber, M., Hujter, M., Tuza, Z.: An upper bound on the number of cliques in a graph. Networks 23, 75\u201383 (1993)","journal-title":"Networks"},{"key":"2532_CR16","first-page":"271","volume":"49","author":"GH Fricke","year":"1998","unstructured":"Fricke, G.H., Hedetniemi, S.T., Jacobs, D.P.: Indpependence and irredundance in k-regular graphs. Ars Comb. 49, 271\u2013279 (1998)","journal-title":"Ars Comb."},{"key":"2532_CR17","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.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"2532_CR18","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"2532_CR19","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. Freeman, San Francisco (1979)"},{"key":"2532_CR20","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on $$P_k$$-free graphs in quasi-polynomial time. CoRR abs arXiv:2005.00690"},{"key":"2532_CR21","first-page":"325","volume":"21","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discrete Math. 21, 325\u2013356 (1984)","journal-title":"Ann. Discrete Math."},{"key":"2532_CR22","doi-asserted-by":"crossref","unstructured":"Grzesik, A., Klimo\u015fov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on P6-free graphs. In: Chan, T.M. (e.), Proceedings of the 18 Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pp. 1257\u20131271. SIAM (2019)","DOI":"10.1137\/1.9781611975482.77"},{"key":"2532_CR23","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"2532_CR24","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Pilipczuk, M., van Leeuwen, E. J.: Independence and efficient domination on P6-free graphs. Proc. SODA 2016, pages 1784\u20131803. ACM Trans. Algorithms 14(1), 3:1\u20133:30 (2018)","DOI":"10.1145\/3147214"},{"key":"2532_CR25","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent sets in $$P_5$$-free graphs in polynomial time. In: Proc. SODA, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"2532_CR26","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.dam.2016.04.012","volume":"231","author":"VV Lozin","year":"2017","unstructured":"Lozin, V.V.: From matchings to independent sets. Discret. Appl. Math. 231, 4\u201314 (2017)","journal-title":"Discret. Appl. Math."},{"key":"2532_CR27","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, RUTCOR Research Report, Rutgers University, 30-2005. J. Discrete Algorithms 6, 595\u2013604 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"2532_CR28","unstructured":"Lozin, V.V., Mosca, R.: Maximum independent sets in planar graphs. RUTCOR Research Report RRR 40-2004"},{"key":"2532_CR29","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.dam.2004.07.006","volume":"146","author":"VV Lozin","year":"2005","unstructured":"Lozin, V.V., Mosca, R.: Independent sets in extensions of $$2K_2$$-free graphs. Discret. Appl. Math. 146, 74\u201380 (2005)","journal-title":"Discret. Appl. Math."},{"key":"2532_CR30","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2012.06.014","volume":"460","author":"VV Lozin","year":"2012","unstructured":"Lozin, V.V., Mosca, R.: Maximum regular subgraphs in $$2P_3$$-free graphs. Theor. Comput. Sci. 460, 26\u201333 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"2532_CR31","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.disopt.2013.08.001","volume":"10","author":"VV Lozin","year":"2013","unstructured":"Lozin, V.V., Mosca, R., Purcell, C.: Sparse regular induced subgraphs in 2P3-free graphs. Discrete Optim. 10, 304\u2013309 (2013)","journal-title":"Discrete Optim."},{"key":"2532_CR32","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2532_CR33","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.ipl.2012.10.004","volume":"113","author":"R Mosca","year":"2013","unstructured":"Mosca, R.: Maximum weight independent set in ($$P_6$$, co-banner)-free graphs. Inf. Process. Lett. 113, 89\u201393 (2013)","journal-title":"Inf. Process. Lett."},{"key":"2532_CR34","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/j.dam.2015.10.023","volume":"216","author":"R Mosca","year":"2017","unstructured":"Mosca, R.: A sufficient condition to extend polynomial results for the maximum independent set problem. Discrete Appl. Math. 216, 281\u2013289 (2017)","journal-title":"Discrete Appl. Math."},{"key":"2532_CR35","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0166-218X(92)90041-8","volume":"35","author":"OJ Murphy","year":"1992","unstructured":"Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35, 167\u2013170 (1992)","journal-title":"Discrete Appl. Math."},{"key":"2532_CR36","first-page":"194","volume":"44","author":"D Nakamura","year":"2001","unstructured":"Nakamura, D., Tamura, A.: A revision of Minty\u2019s algorithm for finding a maximum weight stable set in a claw-free graph. J. Oper. Res. Soc. Jpn. 44, 194\u2013204 (2001)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"2532_CR37","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s10107-019-01461-5","volume":"186","author":"P Nobili","year":"2021","unstructured":"Nobili, P., Sassano, A.: An O($$n^2log(n)$$) algorithm for the weighted stable set problem in claw-free graphs. Math. Progr. 186, 409\u2013437 (2021)","journal-title":"Math. Progr."},{"key":"2532_CR38","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.disopt.2016.01.002","volume":"19","author":"P Nobili","year":"2016","unstructured":"Nobili, P., Sassano, A.: An algorithm for the weighted stable set problem in claw, net-free graphs with $$\\alpha (G) \\ge 4$$. Discrete Optim. 19, 63\u201378 (2016)","journal-title":"Discrete Optim."},{"key":"2532_CR39","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s10107-016-1080-9","volume":"164","author":"P Nobili","year":"2017","unstructured":"Nobili, P., Sassano, A.: An $${{{\\cal{O} }}}(n^2 \\log n)$$ algorithm for the weighted stable set problem in claw-free graphs with $$\\alpha (G) \\le 3$$. Math. Progr. 164, 157\u2013165 (2017)","journal-title":"Math. Progr."},{"key":"2532_CR40","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Pilipczuk, M., Rzazewski, P.: Quasi-polynomial-time algorithm for independent set in $$P_t$$-free graphs via shrinking the space of induced paths. SOSA 204\u2013209 (2021). https:\/\/doi.org\/10.1137\/1.9781611976472.23","DOI":"10.1137\/1.9781611976472.23"},{"key":"2532_CR41","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Commun. Math. Univ. Carolinae 15, 307\u2013309 (1974)","journal-title":"Commun. Math. Univ. Carolinae"},{"key":"2532_CR42","unstructured":"Prisner, E., Graphs with few cliques, Graph Theory, Combinatorics and Algorithms, vol. 1, 2 (Kalamazoo, MI, 1992), pp. 945\u2013956. Wiley-Interscience Publishers, Wiley, New York (1995)"},{"key":"2532_CR43","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 cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discrete Math. 29, 53\u201376 (1980)","journal-title":"Discrete Math."},{"key":"2532_CR44","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all maximal independent sets. SIAM J. Comput. 6, 505\u2013517 (1977)","journal-title":"SIAM J. Comput."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02532-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-022-02532-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02532-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T13:18:02Z","timestamp":1660223882000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-022-02532-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,29]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["2532"],"URL":"https:\/\/doi.org\/10.1007\/s00373-022-02532-9","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2022,7,29]]},"assertion":[{"value":"1 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that he has no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"127"}}