{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:53Z","timestamp":1759638713910,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031159138"},{"type":"electronic","value":"9783031159145"}],"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-15914-5_29","type":"book-chapter","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:14:22Z","timestamp":1664536462000},"page":"398-411","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Induced Disjoint Paths and\u00a0Connected Subgraphs for\u00a0H-Free Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4642-8614","authenticated-orcid":false,"given":"Barnaby","family":"Martin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0797-0512","authenticated-orcid":false,"given":"Siani","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5240-7257","authenticated-orcid":false,"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,1]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Belmonte, R., Golovach, P.A., Heggernes, P., van\u2019t Hof, P., Kaminski, M., Paulusma, D.: Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica 69, 501\u2013521 (2014)","key":"29_CR1","DOI":"10.1007\/s00453-013-9748-5"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: On the complexity of testing for odd holes and induced odd paths. Discret. Math. 90, 85\u201392 (1991)","journal-title":"Discret. Math."},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.tcs.2007.09.031","volume":"389","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theoret. Comput. Sci. 389, 295\u2013306 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00453-015-9989-6","volume":"75","author":"E Camby","year":"2016","unstructured":"Camby, E., Schaudt, O.: A new characterization of $${P}_k$$-free graphs. Algorithmica 75, 205\u2013217 (2016)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: a survey of applications. Proc. AMS-IMS-SIAM Joint Summer Res. Conf. Contemp. Math. 89, 1\u201318 (1989)","key":"29_CR5","DOI":"10.1090\/conm\/089\/1006472"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00453-010-9468-z","volume":"62","author":"J Fiala","year":"2012","unstructured":"Fiala, J., Kami\u0144ski, M., Lidick\u00fd, B., Paulusma, D.: The $$k$$-in-a-Path problem for claw-free graphs. Algorithmica 62, 499\u2013519 (2012)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on $${P}_k$$-free graphs in quasi-polynomial time. In: Proceedings of the FOCS 2020, pp. 613\u2013624 (2020)","key":"29_CR7","DOI":"10.1109\/FOCS46700.2020.00063"},{"doi-asserted-by":"crossref","unstructured":"Gartland, P., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Finding large induced sparse subgraphs in $${C}_{\\>t}$$-free graphs in quasipolynomial time. In: Proceedings of the STOC 2021, pp. 330\u2013341 (2021)","key":"29_CR8","DOI":"10.1145\/3406325.3451034"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/140963200","volume":"29","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in claw-free graphs. SIAM J. Discret. Math. 29, 348\u2013375 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2016.06.003","volume":"640","author":"PA Golovach","year":"2016","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in circular-arc graphs in linear time. Theoret. Comput. Sci. 640, 70\u201383 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.jcss.2021.10.003","volume":"124","author":"PA Golovach","year":"2022","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-free graphs. J. Comput. Syst. Sci. 124, 170\u2013191 (2022)","journal-title":"J. Comput. Syst. Sci."},{"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 the SODA 2019, pp. 1257\u20131271 (2019)","key":"29_CR12","DOI":"10.1137\/1.9781611975482.77"},{"doi-asserted-by":"crossref","unstructured":"van\u2019t Hof, P., Paulusma, D.: A new characterization of $${P}_6$$-free graphs. Discrete Appl. Math. 158, 731\u2013740 (2010)","key":"29_CR13","DOI":"10.1016\/j.dam.2008.08.025"},{"doi-asserted-by":"crossref","unstructured":"van\u2019t Hof, P., Paulusma, D., Woeginger, G.J.: Partitioning graphs into connected parts. Theoret. Comput. Sci. 410, 4834\u20134843 (2009)","key":"29_CR14","DOI":"10.1016\/j.tcs.2009.06.028"},{"doi-asserted-by":"crossref","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Mim-width I. induced path problems. Discrete Appl. Math. 278, 153\u2013168 (2020)","key":"29_CR15","DOI":"10.1016\/j.dam.2019.06.026"},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00453-019-00601-9","volume":"82","author":"M Johnson","year":"2020","unstructured":"Johnson, M., Paesani, G., Paulusma, D.: Connected Vertex Cover for $$(s{P}_1+{P}_5)$$-free graphs. Algorithmica 82, 20\u201340 (2020)","journal-title":"Algorithmica"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1016\/j.jcss.2011.10.004","volume":"78","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y.: A linear time algorithm for the induced disjoint paths problem in planar graphs. J. Comput. Syst. Sci. 78, 670\u2013680 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2021.10.019","volume":"898","author":"W Kern","year":"2022","unstructured":"Kern, W., Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Disjoint paths and connected subgraphs for $$H$$-free graphs. Theoret. Comput. Sci. 898, 59\u201368 (2022)","journal-title":"Theoret. Comput. Sci."},{"unstructured":"Kern, W., Paulusma, D.: Contracting to a longest path in $${H}$$-free graphs. Proc. ISAAC 2020, LIPIcs 181, 22:1\u201322:18 (2020)","key":"29_CR19"},{"doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Proceedings of the SODA 2009, pp. 1146\u20131155 (2009)","key":"29_CR20","DOI":"10.1137\/1.9781611973068.124"},{"key":"29_CR21","doi-asserted-by":"publisher","first-page":"3540","DOI":"10.1016\/j.dam.2009.02.015","volume":"157","author":"B L\u00e9v\u00eaque","year":"2009","unstructured":"L\u00e9v\u00eaque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discret. Appl. Math. 157, 3540\u20133551 (2009)","journal-title":"Discret. Appl. Math."},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0166-218X(97)00020-6","volume":"78","author":"WN Li","year":"1997","unstructured":"Li, W.N.: Two-segmented channel routing is strong NP-complete. Discret. Appl. Math. 78, 291\u2013298 (1997)","journal-title":"Discret. Appl. Math."},{"key":"29_CR23","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"J Lynch","year":"1975","unstructured":"Lynch, J.: The equivalence of theorem proving and the interconnection problem. SIGDA Newsl. 5, 31\u201336 (1975)","journal-title":"SIGDA Newsl."},{"doi-asserted-by":"crossref","unstructured":"Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Few induced disjoint paths for $${H}$$-free graphs. Proc. ISCO 2022, LNCS (to appear)","key":"29_CR24","DOI":"10.1007\/978-3-031-18530-4_7"},{"key":"29_CR25","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. Theor. Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theor. Ser. B"},{"unstructured":"Paesani, G., Paulusma, D., Rz\u0105\u017cewski, P.: Feedback Vertex Set and Even Cycle Transversal for $${H}$$-free graphs: finding large block graphs. SIAM J. Discret. Math. (to appear)","key":"29_CR26"},{"doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Quasi-polynomial-time algorithm for independent set in $${P}_t$$-free graphs via shrinking the space of induced paths. In: Proceedings of the SOSA 2021, pp. 204\u2013209 (2021)","key":"29_CR27","DOI":"10.1137\/1.9781611976472.23"},{"doi-asserted-by":"crossref","unstructured":"Radovanovi\u0107, M., Trotignon, N., Vus\u0306kovi\u0107, K.: The (theta, wheel)-free graphs Part IV: induced paths and cycles. J. Comb. Theor. Ser. B 146, 495\u2013531 (2021)","key":"29_CR28","DOI":"10.1016\/j.jctb.2020.06.002"},{"doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63, 65\u2013110 (1995)","key":"29_CR29","DOI":"10.1006\/jctb.1995.1006"},{"doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216\u2013226 (1978)","key":"29_CR30","DOI":"10.1145\/800133.804350"},{"key":"29_CR31","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Shibi","year":"1980","unstructured":"Shibi, N.: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discret. Math. 29, 53\u201376 (1980)","journal-title":"Discret. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15914-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T00:53:51Z","timestamp":1728089631000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15914-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159138","9783031159145"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15914-5_29","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":"1 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcbingen","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":"22 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.inf.uni-tuebingen.de\/wg2022\/","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":"96","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":"32","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":"33% - 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":"12","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)"}}]}}