{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:42:05Z","timestamp":1742949725185,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030799861"},{"type":"electronic","value":"9783030799878"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-79987-8_17","type":"book-chapter","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:05:05Z","timestamp":1625007905000},"page":"237-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Vertex Cover at Distance on H-Free Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9522-3770","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Dallard","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7616-7067","authenticated-orcid":false,"given":"Mirza","family":"Krbezlija","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8222-8097","authenticated-orcid":false,"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"17_CR1","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313. Gor\u2019kov. Gos. Univ., Gorki (1982)"},{"issue":"1\u20133","key":"17_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135(1\u20133), 3\u201316 (2004). https:\/\/doi.org\/10.1016\/S0166-218X(02)00290-1","journal-title":"Discrete Appl. Math."},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.dam.2015.05.010","volume":"194","author":"JD Alvarado","year":"2015","unstructured":"Alvarado, J.D., Dantas, S., Rautenbach, D.: Distance $$k$$-domination, distance $$k$$-guarding, and distance $$k$$-vertex cover of maximal outerplanar graphs. Discrete Appl. Math. 194, 154\u2013159 (2015). https:\/\/doi.org\/10.1016\/j.dam.2015.05.010","journal-title":"Discrete Appl. Math."},{"key":"17_CR4","unstructured":"Bacs\u00f3, G., Marx, D., Tuza, Z.: $$H$$-free graphs, independent sets, and subexponential-time algorithms. In: 11th International Symposium on Parameterized and Exact Computation, LIPIcs. Leibniz International Proceedings o Inform., vol. 63, pp. Art. No. 3, 12, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"17_CR5","doi-asserted-by":"publisher","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent set for $$\\ell $$claw-free graphs in polynomial time. Discrete Appl. Math. 237, 57\u201364 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.11.029","DOI":"10.1016\/j.dam.2017.11.029"},{"issue":"13\u201314","key":"17_CR6","doi-asserted-by":"publisher","first-page":"1943","DOI":"10.1016\/j.dam.2013.02.024","volume":"161","author":"B Bre\u0161ar","year":"2013","unstructured":"Bre\u0161ar, B., Jakovac, M., Katreni\u010d, J., Semani\u0161in, G., Taranenko, A.: On the vertex $$k$$-path cover. Discrete Appl. Math. 161(13\u201314), 1943\u20131949 (2013). https:\/\/doi.org\/10.1016\/j.dam.2013.02.024","journal-title":"Discrete Appl. Math."},{"issue":"12","key":"17_CR7","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum $$k$$-path vertex cover. Discrete Appl. Math. 159(12), 1189\u20131195 (2011). https:\/\/doi.org\/10.1016\/j.dam.2011.04.008","journal-title":"Discrete Appl. Math."},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-17461-2_17","volume-title":"Combinatorial Optimization and Applications","author":"AH Busch","year":"2010","unstructured":"Busch, A.H., Dragan, F.F., Sritharan, R.: New min-max theorems for weakly chordal and dually chordal graphs. In: Wu, W., Daescu, O. (eds.) COCOA 2010. LNCS, vol. 6509, pp. 207\u2013218. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17461-2_17"},{"issue":"1","key":"17_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00453-015-9989-6","volume":"75","author":"E Camby","year":"2015","unstructured":"Camby, E., Schaudt, O.: A new characterization of $$P_k$$-free graphs. Algorithmica 75(1), 205\u2013217 (2015). https:\/\/doi.org\/10.1007\/s00453-015-9989-6","journal-title":"Algorithmica"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.dam.2014.08.040","volume":"181","author":"S Canales","year":"2015","unstructured":"Canales, S., Hern\u00e1ndez, G., Martins, M., Matos, I.: Distance domination, guarding and covering of maximal outerplanar graphs. Discrete Appl. Math. 181, 41\u201349 (2015). https:\/\/doi.org\/10.1016\/j.dam.2014.08.040","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"17_CR11","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/0605034","volume":"5","author":"GJ Chang","year":"1984","unstructured":"Chang, G.J., Nemhauser, G.L.: The $$k$$-domination and $$k$$-stability problems on sun-free chordal graphs. SIAM J. Algebraic Discrete Methods 5(3), 332\u2013345 (1984)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"3","key":"17_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discrete Appl. Math. 3(3), 163\u2013174 (1981). https:\/\/doi.org\/10.1016\/0166-218X(81)90013-5","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"17_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000). https:\/\/doi.org\/10.1007\/s002249910009","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"17_CR14","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1002\/jgt.22426","volume":"91","author":"Z Dvo\u0159\u00e1k","year":"2019","unstructured":"Dvo\u0159\u00e1k, Z.: On distance $$r$$-dominating and $$2r$$-independent sets in sparse graphs. J. Graph Theory 91(2), 162\u2013173 (2019). https:\/\/doi.org\/10.1002\/jgt.22426","journal-title":"J. Graph Theory"},{"issue":"1","key":"17_CR15","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s10878-012-9594-4","volume":"27","author":"H Eto","year":"2013","unstructured":"Eto, H., Guo, F., Miyano, E.: Distance-$$d$$ independent set problems for bipartite and chordal graphs. J. Combin. Optimizat. 27(1), 88\u201399 (2013). https:\/\/doi.org\/10.1007\/s10878-012-9594-4","journal-title":"J. Combin. Optimizat."},{"key":"17_CR16","doi-asserted-by":"publisher","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on $$P_k$$-free graphs in quasi-polynomial time. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 613\u2013624, IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00063","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"17_CR17","doi-asserted-by":"publisher","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $$P_6$$-free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1257\u20131271, SIAM, Philadelphia, PA (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.77","DOI":"10.1137\/1.9781611975482.77"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Horton, J.D., L\u00f3pez-Ortiz, A.: On the number of distributed measurement points for network tomography. In: Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference, IMC 2003, Miami Beach, FL, USA, October 27\u201329, 2003, pp. 204\u2013209, ACM (2003)","DOI":"10.1145\/948205.948231"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.tcs.2019.09.012","volume":"796","author":"L Jaffke","year":"2019","unstructured":"Jaffke, L., Kwon, O.J., Str\u00f8mme, T.J.F., Telle, J.A.: Mim-width III. Graph powers and generalized distance domination problems. Theoret. Comput. Sci. 796, 216\u2013236 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.09.012","journal-title":"Theoret. Comput. Sci."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations, Proceedings of the Symposium IBM Thomas Journal Watson Research Center, Yorktown Heights, N.Y., 1972, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"17_CR21","doi-asserted-by":"publisher","unstructured":"Katsikarelis, I., Lampis, M., Paschos, V.T.: Structurally parameterized $$d$$-scattered set. In: Brandst\u00e4dt, A., K\u00f6hler, E., Meer, K. (eds.) Graph-Theoretic Concepts in Computer Science, LNCS, vol. 11159, pp. 292\u2013305, Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_24","DOI":"10.1007\/978-3-030-00256-5_24"},{"key":"17_CR22","doi-asserted-by":"publisher","unstructured":"Lee, E.: Partitioning a graph into small pieces with applications to path transversal. Math. Program. (1), 1\u201319 (2018). https:\/\/doi.org\/10.1007\/s10107-018-1255-7","DOI":"10.1007\/s10107-018-1255-7"},{"key":"17_CR23","first-page":"299","volume":"100","author":"M Lema\u0144ska","year":"2016","unstructured":"Lema\u0144ska, M.: On the minimum vertex $$k$$-path cover of trees. Util. Math. 100, 299\u2013307 (2016)","journal-title":"Util. Math."},{"key":"17_CR24","doi-asserted-by":"publisher","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in $$P_5$$-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570\u2013581. ACM, New York (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.43","DOI":"10.1137\/1.9781611973402.43"},{"key":"17_CR25","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02289199","volume":"15","author":"RD Luce","year":"1950","unstructured":"Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15, 169\u2013190 (1950). https:\/\/doi.org\/10.1007\/BF02289199","journal-title":"Psychometrika"},{"key":"17_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1007\/978-3-662-48350-3_72","volume-title":"Algorithms - ESA 2015","author":"D Marx","year":"2015","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 865\u2013877. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72"},{"issue":"1","key":"17_CR27","doi-asserted-by":"publisher","first-page":"225","DOI":"10.2140\/pjm.1975.61.225","volume":"61","author":"A Meir","year":"1975","unstructured":"Meir, A., Moon, J.W.: Relations between packing and covering numbers of a tree. Pacific J. Math. 61(1), 225\u2013233 (1975)","journal-title":"Pacific J. Math."},{"issue":"3","key":"17_CR28","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. Combin. Theory Ser. B 28(3), 284\u2013304 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90074-X","journal-title":"J. Combin. Theory Ser. B"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13(2), 161\u2013173 (1979)","DOI":"10.1007\/BF00139635"},{"key":"17_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-662-53536-3_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P Montealegre","year":"2016","unstructured":"Montealegre, P., Todinca, I.: On distance-d independent set and other problems in graphs with \u201cfew\u2019\u2019 minimal separators. In: Heggernes, P. (ed.) WG 2016. LNCS, vol. 9941, pp. 183\u2013194. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53536-3_16"},{"key":"17_CR31","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Siebertz, S.: Kernelization and approximation of distance-$$r$$ independent sets on nowhere dense graphs. Eur. J. Combin. 94, 103309, 19 (2021). https:\/\/doi.org\/10.1016\/j.ejc.2021.103309","DOI":"10.1016\/j.ejc.2021.103309"},{"key":"17_CR32","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carolinae 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"17_CR33","unstructured":"Sasaki, M., Zhao, L., Nagamochi, H.: Security-aware beacon based network monitoring. In: 2008 11th IEEE Singapore International Conference on Communication Systems, pp. 527\u2013531. IEEE (2008)"},{"issue":"1","key":"17_CR34","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(1), 53\u201376 (1980). https:\/\/doi.org\/10.1016\/0012-365X(90)90287-R","journal-title":"Discrete Math."},{"issue":"1","key":"17_CR35","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inform. Process. Lett. 15(1), 14\u201319 (1982). https:\/\/doi.org\/10.1016\/0020-0190(82)90077-1","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"17_CR36","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980). https:\/\/doi.org\/10.1137\/0138030","journal-title":"SIAM J. Appl. Math."},{"key":"17_CR37","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.ipl.2016.11.003","volume":"119","author":"Z Zhang","year":"2017","unstructured":"Zhang, Z., Li, X., Shi, Y., Nie, H., Zhu, Y.: PTAS for minimum $$k$$-path vertex cover in ball graph. Inform. Process. Lett. 119, 9\u201313 (2017). https:\/\/doi.org\/10.1016\/j.ipl.2016.11.003","journal-title":"Inform. Process. Lett."}],"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-030-79987-8_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:11:48Z","timestamp":1625008308000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79987-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030799861","9783030799878"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79987-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"30 June 2021","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":"Ottawa, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2021.eecs.uottawa.ca\/","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":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"107","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":"38","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":"36% - 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.1","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":"9.1","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)"}},{"value":"The workshop was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}