{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:23Z","timestamp":1772119403498,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T00:00:00Z","timestamp":1686182400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T00:00:00Z","timestamp":1686182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s00453-023-01138-8","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T07:02:11Z","timestamp":1686207731000},"page":"757-781","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["1-Extendability of Independent Sets"],"prefix":"10.1007","volume":"86","author":[{"given":"Pierre","family":"Berg\u00e9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Busson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl","family":"Feghali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"1138_CR1","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. Comb. Algebr. Methods Appl. Math. 3\u201313 (1982)"},{"issue":"5","key":"1138_CR2","first-page":"801","volume":"101","author":"K Angaleeswari","year":"2015","unstructured":"Angaleeswari, K., Sumathi, P., Swaminathan, V.: $$k$$-extendability in graphs. Int. J. Pure Appl. Math. 101(5), 801\u2013809 (2015)","journal-title":"Int. J. Pure Appl. Math."},{"issue":"6","key":"1138_CR3","first-page":"35","volume":"109","author":"K Angaleeswari","year":"2016","unstructured":"Angaleeswari, K., Sumathi, P., Swaminathan, V.: Weakly $$k$$-extendable graphs. Int. J. Pure Appl. Math. 109(6), 35\u201340 (2016)","journal-title":"Int. J. Pure Appl. Math."},{"key":"1138_CR4","first-page":"108","volume":"108","author":"C Berge","year":"1981","unstructured":"Berge, C.: Some common properties for regularizable graphs, edge-critical graphs and B-graphs. Graph Theory Algorithms Lect. Notes Comput. Sci. 108, 108\u2013123 (1981)","journal-title":"Graph Theory Algorithms Lect. Notes Comput. Sci."},{"issue":"8","key":"1138_CR5","doi-asserted-by":"publisher","first-page":"2360","DOI":"10.1007\/s00453-020-00730-6","volume":"82","author":"\u00c9 Bonnet","year":"2020","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in $$H$$-free graphs. Algorithmica 82(8), 2360\u20132394 (2020)","journal-title":"Algorithmica"},{"key":"1138_CR6","first-page":"49:1","volume":"149","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Bousquet, N., Thomass\u00e9, S., Watrigant, R.: When maximum stable set can be solved in FPT time. Proc. ISAAC 149, 49:1-49:22 (2019)","journal-title":"Proc. ISAAC"},{"key":"1138_CR7","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Slater, P. J.: A note on well-covered graphs. In: Quo Vadis, Graph Theory? Annals of Discrete Mathematics, vol. 55, pp. 179\u2013181. Elsevier, Amsterdam (1993)","DOI":"10.1016\/S0167-5060(08)70387-X"},{"issue":"1\u20133","key":"1138_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1\u20133), 165\u2013177 (1990)","journal-title":"Discret. Math."},{"key":"1138_CR9","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":"1138_CR10","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jda.2011.12.012","volume":"14","author":"KK Dabrowski","year":"2012","unstructured":"Dabrowski, K.K., Lozin, V.V., M\u00fcller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms 14, 207\u2013213 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"1138_CR11","first-page":"216","volume":"6196","author":"M de Berg","year":"2010","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. Proc. COCOON 6196, 216\u2013225 (2010)","journal-title":"Proc. COCOON"},{"issue":"1\u20133","key":"1138_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0012-365X(94)90253-4","volume":"126","author":"N Dean","year":"1994","unstructured":"Dean, N., Zito, J.S.: Well-covered graphs and extendability. Discret. Math. 126(1\u20133), 67\u201380 (1994)","journal-title":"Discret. Math."},{"key":"1138_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.jnca.2017.03.001","volume":"87","author":"B Ducourthial","year":"2017","unstructured":"Ducourthial, B., Mottelet, S., Busson, A.: Improving fairness between close Wi-Fi access points. J. Netw. Comput. Appl. 87, 87\u201399 (2017)","journal-title":"J. Netw. Comput. Appl."},{"issue":"2","key":"1138_CR14","first-page":"273","volume":"72","author":"AS Finbow","year":"2018","unstructured":"Finbow, A.S., Whitehead, C.A.: Constructions for well-covered graphs. Austral. J. Comb. 72(2), 273\u2013289 (2018)","journal-title":"Austral. J. Comb."},{"issue":"3","key":"1138_CR15","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. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"1138_CR16","doi-asserted-by":"crossref","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $$P_6$$-free graphs. In: Proceedings of SODA, pp. 1257\u20131271. SIAM (2019)","DOI":"10.1137\/1.9781611975482.77"},{"issue":"3","key":"1138_CR17","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s10878-017-0226-x","volume":"35","author":"J Hackfeld","year":"2018","unstructured":"Hackfeld, J., Koster, A.: The matching extension problem in general graphs is co-NP-complete. J. Comb. Optim. 35(3), 853\u2013859 (2018)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"1138_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1138_CR19","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1109\/TNET.2015.2415465","volume":"24","author":"R Laufer","year":"2016","unstructured":"Laufer, R., Kleinrock, L.: The capacity of wireless CSMA\/CA networks. IEEE\/ACM Trans. Netw. 24(3), 1518\u20131532 (2016)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"9","key":"1138_CR20","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1109\/TMC.2010.89","volume":"9","author":"SC Liew","year":"2010","unstructured":"Liew, S.C., Kai, C.H., Leung, H.C., Wong, P.: Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Trans. Mobile Comput. 9(9), 1319\u20131331 (2010)","journal-title":"IEEE Trans. Mobile Comput."},{"issue":"1","key":"1138_CR21","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"B Mohar","year":"2001","unstructured":"Mohar, B.: Face covers and the genus problem for apex graphs. J. Comb. Theory Ser. B 82(1), 102\u2013117 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1138_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103309","volume":"94","author":"M Pilipczuk","year":"2021","unstructured":"Pilipczuk, M., Siebertz, S.: Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Eur. J. Comb. 94, 103309 (2021)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"1138_CR23","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0021-9800(70)80011-4","volume":"8","author":"MD Plummer","year":"1970","unstructured":"Plummer, M.D.: Some covering concepts in graphs. J. Comb. Theory 8(1), 91\u201398 (1970)","journal-title":"J. Comb. Theory"},{"key":"1138_CR24","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0012-365X(80)90037-0","volume":"31","author":"MD Plummer","year":"1980","unstructured":"Plummer, M.D.: On $$n$$-extendable graphs. Discrete Math. 31, 201\u2013210 (1980)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"1138_CR25","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0012-365X(92)00485-A","volume":"127","author":"MD Plummer","year":"1994","unstructured":"Plummer, M.D.: Extending matchings in graphs: a survey. Discrete Math. 127(1\u20133), 277\u2013292 (1994)","journal-title":"Discrete Math."},{"key":"1138_CR26","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings in graphs. Comment. Math. Univ. Carol. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"1138_CR27","unstructured":"Ravindra, G.: B-graphs. In: Proceedings of the Symposium Graph Theory, ISI Lecture Notes Calcutta, 4, 268\u2013280 (1976)"},{"key":"1138_CR28","first-page":"20","volume":"2","author":"G Ravindra","year":"1977","unstructured":"Ravindra, G.: Well covered graphs. J. Comb. Inform. Syst. Sci. 2, 20\u201321 (1977)","journal-title":"J. Comb. Inform. Syst. Sci."},{"issue":"3","key":"1138_CR29","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230220304","volume":"22","author":"RS Sankaranarayana","year":"1992","unstructured":"Sankaranarayana, R.S., Stewart, L.K.: Complexity results for well-covered graphs. Networks 22(3), 247\u2013262 (1992)","journal-title":"Networks"},{"issue":"2","key":"1138_CR30","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/jctb.1996.0022","volume":"66","author":"D Tankus","year":"1996","unstructured":"Tankus, D., Tarsi, M.: Well-covered claw-free graphs. J. Comb. Theory Ser. B 66(2), 293\u2013302 (1996)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1138_CR31","unstructured":"The Network Simulator ns-3. https:\/\/www.nsnam.org\/, 2022. Accessed on 30 Sept. 2021"},{"issue":"2","key":"1138_CR32","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"LG Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30(2), 135\u2013140 (1981)","journal-title":"IEEE Trans. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01138-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01138-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01138-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T11:09:54Z","timestamp":1710155394000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01138-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,8]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1138"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01138-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2142423\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,8]]},"assertion":[{"value":"7 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2023","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 authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}