{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:12:39Z","timestamp":1742940759185,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433795"},{"type":"electronic","value":"9783031433801"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_28","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"388-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Tight Algorithms for\u00a0Connectivity Problems Parameterized by\u00a0Modular-Treewidth"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2125-5048","authenticated-orcid":false,"given":"Falko","family":"Hegerfeld","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0193-7239","authenticated-orcid":false,"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 522\u2013539. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.32","DOI":"10.1137\/1.9781611976465.32"},{"key":"28_CR2","unstructured":"Bergougnoux, B.: Matrix decompositions and algorithmic applications to (hyper)graphs. Ph.D. thesis, University of Clermont Auvergne, Clermont-Ferrand, France (2019). https:\/\/tel.archives-ouvertes.fr\/tel-02388683"},{"key":"28_CR3","doi-asserted-by":"publisher","unstructured":"Bergougnoux, B., Dreier, J., Jaffke, L.: A logic-based algorithmic meta-theorem for mim-width, pp. 3282\u20133304 (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch125","DOI":"10.1137\/1.9781611977554.ch125"},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2019.02.030","volume":"782","author":"B Bergougnoux","year":"2019","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: Fast exact algorithms for some connectivity problems parameterized by clique-width. Theor. Comput. Sci. 782, 30\u201353 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.02.030","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"28_CR5","doi-asserted-by":"publisher","first-page":"1881","DOI":"10.1137\/20M1350571","volume":"35","author":"B Bergougnoux","year":"2021","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: More applications of the d-neighbor equivalence: acyclicity and connectivity constraints. SIAM J. Discret. Math. 35(3), 1881\u20131926 (2021). https:\/\/doi.org\/10.1137\/20M1350571","journal-title":"SIAM J. Discret. Math."},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008","journal-title":"Inf. Comput."},{"issue":"1","key":"28_CR7","first-page":"14","volume":"7","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of the maximum cut problem. Nord. J. Comput. 7(1), 14\u201331 (2000)","journal-title":"Nord. J. Comput."},{"key":"28_CR8","doi-asserted-by":"publisher","unstructured":"Bojikian, N., Chekan, V., Hegerfeld, F., Kratsch, S.: Tight bounds for connectivity problems parameterized by cutwidth. In: Berenbrink, P., Bouyer, P., Dawar, A., Kant\u00e9, M.M. (eds.) 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, 7\u20139 March 2023, Hamburg, Germany. LIPIcs, vol. 254, pp. 14:1\u201314:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2023.14","DOI":"10.4230\/LIPIcs.STACS.2023.14"},{"issue":"4","key":"28_CR9","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005). https:\/\/doi.org\/10.1137\/S0097539701385351","journal-title":"SIAM J. Comput."},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. CoRR abs\/1103.0534 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"28_CR11","doi-asserted-by":"publisher","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms 18(2), 17:1\u201317:31 (2022). https:\/\/doi.org\/10.1145\/3506707","DOI":"10.1145\/3506707"},{"issue":"1\u20132","key":"28_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math. Hungar. 18(1\u20132), 25\u201366 (1967)","journal-title":"Acta Math. Hungar."},{"issue":"1","key":"28_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010). https:\/\/doi.org\/10.1016\/j.cosrev.2010.01.001","journal-title":"Comput. Sci. Rev."},{"key":"28_CR14","doi-asserted-by":"publisher","unstructured":"Hegerfeld, F., Kratsch, S.: Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, 10\u201313 March 2020, Montpellier, France. LIPIcs, vol. 154, pp. 29:1\u201329:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.29","DOI":"10.4230\/LIPIcs.STACS.2020.29"},{"key":"28_CR15","doi-asserted-by":"publisher","unstructured":"Hegerfeld, F., Kratsch, S.: Towards exact structural thresholds for parameterized complexity. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, 7\u20139 September 2022, Potsdam, Germany. LIPIcs, vol. 249, pp. 17:1\u201317:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.17","DOI":"10.4230\/LIPIcs.IPEC.2022.17"},{"key":"28_CR16","doi-asserted-by":"publisher","unstructured":"Hegerfeld, F., Kratsch, S.: Tight algorithms for connectivity problems parameterized by clique-width. CoRR abs\/2302.03627 (2023). https:\/\/doi.org\/10.48550\/arXiv.2302.03627, accepted at ESA 2023","DOI":"10.48550\/arXiv."},{"key":"28_CR17","doi-asserted-by":"publisher","unstructured":"Hegerfeld, F., Kratsch, S.: Tight algorithms for connectivity problems parameterized by modular-treewidth. CoRR abs\/2302.14128 (2023). https:\/\/doi.org\/10.48550\/arXiv.2302.14128","DOI":"10.48550\/arXiv.2302.14128"},{"key":"28_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","year":"1994","unstructured":"Kloks, T. (ed.): Treewidth. LNCS, vol. 842. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0045375"},{"key":"28_CR19","doi-asserted-by":"publisher","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, 7\u201310 February 2022, pp. 184\u2013192. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00026","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"28_CR20","doi-asserted-by":"publisher","unstructured":"Kratsch, S., Nelles, F.: Efficient parameterized algorithms on graphs with heterogeneous structure: combining tree-depth and modular-width. CoRR abs\/2209.14429 (2022). https:\/\/doi.org\/10.48550\/arXiv.2209.14429","DOI":"10.48550\/arXiv.2209.14429"},{"issue":"3","key":"28_CR21","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1137\/19M1280326","volume":"34","author":"M Lampis","year":"2020","unstructured":"Lampis, M.: Finer tight bounds for coloring on clique-width. SIAM J. Discret. Math. 34(3), 1538\u20131558 (2020). https:\/\/doi.org\/10.1137\/19M1280326","journal-title":"SIAM J. Discret. Math."},{"key":"28_CR22","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13:1\u201313:30 (2018). https:\/\/doi.org\/10.1145\/3170442","DOI":"10.1145\/3170442"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Luo, W.: Polynomial turing compressions for some graph problems parameterized by modular-width. CoRR abs\/2201.04678 (2022)","DOI":"10.1007\/978-3-031-49190-0_9"},{"key":"28_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-40970-2_1","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"S Mengel","year":"2016","unstructured":"Mengel, S.: Parameterized compilation lower bounds for\u00a0restricted CNF-formulas. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 3\u201312. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40970-2_1"},{"issue":"1","key":"28_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987). https:\/\/doi.org\/10.1007\/BF02579206","journal-title":"Combinatorica"},{"key":"28_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-030-60440-0_3","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J Nederlof","year":"2020","unstructured":"Nederlof, J., Pilipczuk, M., Swennenhuis, C.M.F., W\u0119grzycki, K.: Hamiltonian cycle parameterized by Treedepth in single exponential time and polynomial space. In: Adler, I., M\u00fcller, H. (eds.) WG 2020. LNCS, vol. 12301, pp. 27\u201339. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-60440-0_3"},{"issue":"1","key":"28_CR27","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/s00453-015-0030-x","volume":"76","author":"D Paulusma","year":"2016","unstructured":"Paulusma, D., Slivovsky, F., Szeider, S.: Model counting for CNF formulas of bounded modular treewidth. Algorithmica 76(1), 168\u2013194 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0030-x","journal-title":"Algorithmica"},{"key":"28_CR28","doi-asserted-by":"publisher","unstructured":"Pino, W.J.A., Bodlaender, H.L., van Rooij, J.M.M.: Cut and count and representative sets on branch decompositions. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, 24\u201326 August 2016, Aarhus, Denmark. LIPIcs, vol. 63, pp. 27:1\u201327:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.27","DOI":"10.4230\/LIPIcs.IPEC.2016.27"},{"key":"28_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52"}],"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-43380-1_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T11:57:57Z","timestamp":1703246277000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","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":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}