{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:47:23Z","timestamp":1742978843335,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031066771"},{"type":"electronic","value":"9783031066788"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-06678-8_13","type":"book-chapter","created":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T23:03:31Z","timestamp":1653779011000},"page":"172-185","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["1-Extendability of Independent Sets"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6170-9473","authenticated-orcid":false,"given":"Pierre","family":"Berg\u00e9","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9445-637X","authenticated-orcid":false,"given":"Anthony","family":"Busson","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6727-7213","authenticated-orcid":false,"given":"Carl","family":"Feghali","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6243-5910","authenticated-orcid":false,"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,29]]},"reference":[{"key":"13_CR1","unstructured":"Alekseev, V.: The effect of local constraints on the complexity of determination of the graph independence number. Combin.-Algebraic Methods Appl. Math. 3\u201313 (1982)"},{"issue":"5","key":"13_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":"13_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":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/978-3-642-14031-0_25","volume-title":"Computing and Combinatorics","author":"M de Berg","year":"2010","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 216\u2013225. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14031-0_25"},{"key":"13_CR5","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":"13_CR6","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":"13_CR7","unstructured":"Bonnet, \u00c9., Bousquet, N., Thomass\u00e9, S., Watrigant, R.: When maximum stable set can be solved in FPT time. In: Proceedings of ISAAC, vol. 149, pp. 49:1\u201349:22 (2019)"},{"key":"13_CR8","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 (1993)","DOI":"10.1016\/S0167-5060(08)70387-X"},{"issue":"1\u20133","key":"13_CR9","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":"13_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"},{"issue":"1\u20133","key":"13_CR11","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."},{"issue":"2","key":"13_CR12","first-page":"273","volume":"72","author":"AS Finbow","year":"2018","unstructured":"Finbow, A.S., Whitehead, C.A.: Constructions for well-covered graphs. Aust. J. Combin. 72(2), 273\u2013289 (2018)","journal-title":"Aust. J. Combin."},{"issue":"3","key":"13_CR13","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":"13_CR14","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":"13_CR15","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s10878-017-0226-x","volume":"35","author":"J Hackfeld","year":"2017","unstructured":"Hackfeld, J., Koster, A.M.C.A.: The matching extension problem in general graphs is co-NP-complete. J. Comb. Optim. 35(3), 853\u2013859 (2017). https:\/\/doi.org\/10.1007\/s10878-017-0226-x","journal-title":"J. Comb. Optim."},{"issue":"2","key":"13_CR16","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":"9","key":"13_CR17","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. Mob. Comput. 9(9), 1319\u20131331 (2010)","journal-title":"IEEE Trans. Mob. Comput."},{"issue":"1","key":"13_CR18","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":"13_CR19","unstructured":"The Network Simulator ns-3. https:\/\/www.nsnam.org\/. Accessed 30 Sept 2021"},{"issue":"1","key":"13_CR20","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. Combin. Theory 8(1), 91\u201398 (1970)","journal-title":"J. Combin. Theory"},{"key":"13_CR21","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":"13_CR22","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. Discret. Math. 127(1\u20133), 277\u2013292 (1994)","journal-title":"Discret. Math."},{"key":"13_CR23","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings in graphs. Commentationes Math. Univ. Carolinae 15, 307\u2013309 (1974)","journal-title":"Commentationes Math. Univ. Carolinae"},{"key":"13_CR24","unstructured":"Ravindra, G.: B-graphs. In: Proceedings of Symposium on Graph Theory, ISI Lecture Notes Calcutta, vol. 4, pp. 268\u2013280 (1976)"},{"key":"13_CR25","first-page":"20","volume":"2","author":"G Ravindra","year":"1977","unstructured":"Ravindra, G.: Well covered graphs. J. Combin. Inform. System Sci. 2, 20\u201321 (1977)","journal-title":"J. Combin. Inform. System Sci."},{"issue":"3","key":"13_CR26","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":"13_CR27","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. Combin. Theory Ser. B 66(2), 293\u2013302 (1996)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"13_CR28","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":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-06678-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T23:06:13Z","timestamp":1653779173000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06678-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031066771","9783031066788"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06678-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 May 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"33","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.informatik.uni-trier.de\/iwoca-2022","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"86","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}