{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:10:46Z","timestamp":1784110246832,"version":"3.55.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T00:00:00Z","timestamp":1703808000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T00:00:00Z","timestamp":1703808000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100023890","name":"Technische Universit\u00e4t Hamburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100023890","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"abstract":"Abstract<\/jats:title>The leafage of a chordal graph G<\/jats:italic> is the minimum integer $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that G<\/jats:italic> can be realized as an intersection graph of subtrees of a tree with $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond\u00a0[ESA\u00a02018, Algorithmica\u00a02020] proved, among other things, that Dominating Set<\/jats:sc> on chordal graphs admits an algorithm running in time $$2^{\\mathcal {O}(\\ell ^2)} \\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u2113<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present a conceptually much simpler algorithm that runs in time $$2^{\\mathcal {O}(\\ell )} \\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We extend our approach to obtain similar results for Connected Dominating Set<\/jats:sc> and Steiner Tree<\/jats:sc>. We then consider the two classical cut problems MultiCut with Undeletable Terminals<\/jats:sc> and Multiway Cut with Undeletable Terminals<\/jats:sc>. We prove that the former is [1]-hard when parameterized by the leafage and complement this result by presenting a simple $$n^{\\mathcal {O}(\\ell )}$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals<\/jats:sc> on chordal graphs can be solved, in contrast, in $$n^{{{\\mathcal {O}}}(1)}$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time.<\/jats:p>","DOI":"10.1007\/s00453-023-01196-y","type":"journal-article","created":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T13:02:17Z","timestamp":1703854937000},"page":"1428-1474","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Domination and Cut Problems on Chordal Graphs with Bounded Leafage"],"prefix":"10.1007","volume":"86","author":[{"given":"Esther","family":"Galby","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philipp","family":"Schepper","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prafullkumar","family":"Tale","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,12,29]]},"reference":[{"key":"1196_CR1","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1016\/j.dam.2013.04.019","volume":"164","author":"L Alc\u00f3n","year":"2014","unstructured":"Alc\u00f3n, L.: On asteroidal sets in chordal graphs. Discret. Appl. Math. 164, 482\u2013491 (2014). https:\/\/doi.org\/10.1016\/j.dam.2013.04.019","journal-title":"Discret. Appl. Math."},{"key":"1196_CR2","doi-asserted-by":"crossref","unstructured":"Arvind, V., Nedela, R., Ponomarenko, I., Zeman, P.: Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable. CoRR, abs\/2107.10689, (2021). arXiv:2107.10689","DOI":"10.1007\/978-3-031-15914-5_3"},{"key":"1196_CR3","doi-asserted-by":"publisher","unstructured":"Balakrishnan, H., Rajaraman, A., Rangan, C.P.: Connected domination and steiner set on asteroidal triple-free graphs. In Frank K. H.\u00a0A. D., J\u00f6rg-R\u00fcdiger, S., Nicola, S., Sue W. (eds.) Algorithms and Data Structures, Third Workshop, WADS \u201993, Montr\u00e9al, Canada, August 11-13, 1993, Proceedings, volume 709 of Lecture Notes in Computer Science, pp. 131\u2013141. Springer (1993). https:\/\/doi.org\/10.1007\/3-540-57155-8_242","DOI":"10.1007\/3-540-57155-8_242"},{"issue":"3","key":"1196_CR4","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1002\/net.21975","volume":"77","author":"KD Barnetson","year":"2021","unstructured":"Barnetson, K.D., Burgess, A.C., Enright, J.A., Howell, J., Pike, D.A., Ryan, B.: The firebreak problem. Networks 77(3), 372\u2013382 (2021). https:\/\/doi.org\/10.1002\/net.21975","journal-title":"Networks"},{"issue":"4","key":"1196_CR5","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-020-09967-8","volume":"65","author":"R Belmonte","year":"2021","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y., Sikora, F.: Token sliding on split graphs. Theory Comput. Syst. 65(4), 662\u2013686 (2021). https:\/\/doi.org\/10.1007\/s00224-020-09967-8","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"1196_CR6","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."},{"issue":"5","key":"1196_CR7","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1007\/s00453-022-00936-w","volume":"84","author":"B Bergougnoux","year":"2022","unstructured":"Bergougnoux, B., Papadopoulos, C., Telle, J.A.: Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. Algorithmica 84(5), 1385\u20131417 (2022). https:\/\/doi.org\/10.1007\/s00453-022-00936-w","journal-title":"Algorithmica"},{"issue":"1","key":"1196_CR8","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"AA Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19(1), 37\u201340 (1984). https:\/\/doi.org\/10.1016\/0020-0190(84)90126-1","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1196_CR9","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/140961808","volume":"47","author":"N Bousquet","year":"2018","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. SIAM J. Comput. 47(1), 166\u2013207 (2018). https:\/\/doi.org\/10.1137\/140961808","journal-title":"SIAM J. Comput."},{"key":"1196_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"BM Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.01.009","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1196_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterisation of rigid circuit graphs. Discret. Math. 9(3), 205\u2013212 (1974). https:\/\/doi.org\/10.1016\/0012-365X(74)90002-8","journal-title":"Discret. Math."},{"key":"1196_CR12","doi-asserted-by":"publisher","unstructured":"Cao, Y.: Linear recognition of almost interval graphs. In: Robert, K. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1096\u20131115. SIAM, (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch77","DOI":"10.1137\/1.9781611974331.ch77"},{"issue":"6","key":"1196_CR13","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M-S Chang","year":"1998","unstructured":"Chang, M.-S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671\u20131694 (1998). https:\/\/doi.org\/10.1137\/S0097539792238431","journal-title":"SIAM J. Comput."},{"key":"1196_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2012.12.006","volume":"168","author":"S Chaplick","year":"2014","unstructured":"Chaplick, S., Stacho, J.: The vertex leafage of chordal graphs. Discret. Appl. Math. 168, 14\u201325 (2014). https:\/\/doi.org\/10.1016\/j.dam.2012.12.006","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"1196_CR15","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2700209","volume":"11","author":"RH Chitnis","year":"2015","unstructured":"Chitnis, R.H., Cygan, M., Hajiaghayi, M.T., Marx, D.: Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms 11(4), 28:1-28:28 (2015). https:\/\/doi.org\/10.1145\/2700209","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"1196_CR16","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/12086217X","volume":"42","author":"R Chitnis","year":"2013","unstructured":"Chitnis, R., Hajiaghayi, M.T., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput. 42(4), 1674\u20131696 (2013). https:\/\/doi.org\/10.1137\/12086217X","journal-title":"SIAM J. Comput."},{"key":"1196_CR17","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":"1196_CR18","doi-asserted-by":"publisher","unstructured":"de Figueiredo, C. M., Lopes, R., de Melo, A. A., Silva, A.: Parameterized algorithms for steiner tree and dominating set: Bounding the leafage by the vertex leafage. In: Petra, M., Rahman, M. S., Slamin, (eds.) WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, Proceedings, volume 13174 of Lecture Notes in Computer Science, pp. 251\u2013262. Springer, (2022). https:\/\/doi.org\/10.1007\/978-3-030-96731-4_21","DOI":"10.1007\/978-3-030-96731-4_21"},{"key":"1196_CR19","series-title":"volume 173 of Graduate texts in mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. volume 173 of Graduate texts in mathematics, 4th edn. Springer, Berlin (2012)","edition":"4"},{"issue":"4","key":"1196_CR20","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/s00453-016-0127-x","volume":"76","author":"PG Drange","year":"2016","unstructured":"Drange, P.G., Dregi, M.S., van \u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016). https:\/\/doi.org\/10.1007\/s00453-016-0127-x","journal-title":"Algorithmica"},{"issue":"9","key":"1196_CR21","doi-asserted-by":"publisher","first-page":"2432","DOI":"10.1007\/s00453-020-00692-9","volume":"82","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.-F.: On the tractability of optimization problems on H-graphs. Algorithmica 82(9), 2432\u20132473 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00692-9","journal-title":"Algorithmica"},{"issue":"1","key":"1196_CR22","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/s00453-012-9731-6","volume":"69","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69(1), 216\u2013231 (2014). https:\/\/doi.org\/10.1007\/s00453-012-9731-6","journal-title":"Algorithmica"},{"key":"1196_CR23","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Hromkovic, J., Nagl, M., Westfechtel, B. (eds.) Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG 2004, Bad Honnef, Germany, Revised Papers, volume 3353 of Lecture Notes in Computer Science, pages 245\u2013256. Springer, (2004). https:\/\/doi.org\/10.1007\/978-3-540-30559-0_21","DOI":"10.1007\/978-3-540-30559-0_21"},{"key":"1196_CR24","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-5","journal-title":"Can. J. Math."},{"key":"1196_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in tree are exactly the chordal graphs. J. Comb. Theory Ser. B (1974). https:\/\/doi.org\/10.1016\/0095-8956(74)90094-X","journal-title":"J. Comb. Theory Ser. B"},{"key":"1196_CR26","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964). https:\/\/doi.org\/10.4153\/CJM-1964-055-5","journal-title":"Can. J. Math."},{"issue":"3","key":"1196_CR27","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/140975279","volume":"29","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Heggernes, P., van\u2019t Hof, P., Paul, C.: Hadwiger number of graphs with small chordality. SIAM J. Discret. Math. 29(3), 1427\u20131451 (2015). https:\/\/doi.org\/10.1137\/140975279","journal-title":"SIAM J. Discret. Math."},{"key":"1196_CR28","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier, Amsterdam (2004)"},{"issue":"2","key":"1196_CR29","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ejor.2007.02.014","volume":"186","author":"J Guo","year":"2008","unstructured":"Guo, J., H\u00fcffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. Eur. J. Oper. Res. 186(2), 542\u2013553 (2008). https:\/\/doi.org\/10.1016\/j.ejor.2007.02.014","journal-title":"Eur. J. Oper. Res."},{"key":"1196_CR30","doi-asserted-by":"publisher","unstructured":"Habib, M., Stacho, J.: Polynomial-time algorithm for the leafage of chordal graphs. In: Amos, F., Peter, S. (eds.) Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 290\u2013300. Springer, (2009). https:\/\/doi.org\/10.1007\/978-3-642-04128-0_27","DOI":"10.1007\/978-3-642-04128-0_27"},{"issue":"5","key":"1196_CR31","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1016\/j.ejc.2011.09.031","volume":"33","author":"M Habib","year":"2012","unstructured":"Habib, M., Stacho, J.: Reduced clique graphs of chordal graphs. Eur. J. Comb. 33(5), 712\u2013735 (2012). https:\/\/doi.org\/10.1016\/j.ejc.2011.09.031","journal-title":"Eur. J. Comb."},{"key":"1196_CR32","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.dam.2021.08.034","volume":"303","author":"W Hochst\u00e4ttler","year":"2021","unstructured":"Hochst\u00e4ttler, W., Hurink, J.L., Manthey, B., Paulusma, D., Peis, B., Still, G.: In memoriam walter kern. Discret. Appl. Math. 303, 2\u20133 (2021). https:\/\/doi.org\/10.1016\/j.dam.2021.08.034","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1196_CR33","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/s00453-010-9411-3","volume":"61","author":"K Ioannidou","year":"2011","unstructured":"Ioannidou, K., Mertzios, G.B., Nikolopoulos, S.D.: The longest path problem has a polynomial solution on interval graphs. Algorithmica 61(2), 320\u2013341 (2011). https:\/\/doi.org\/10.1007\/s00453-010-9411-3","journal-title":"Algorithmica"},{"key":"1196_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.09.006","volume":"704","author":"DY Kang","year":"2017","unstructured":"Kang, D.Y., Kwon, O.J., Str\u00f8mme, T.J., Telle, J.A.: A width parameter useful for chordal and co-comparability graphs. Theor. Comput. Sci. 704, 1\u201317 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.09.006","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1196_CR35","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Finding Hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201\u2013206 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90050-X","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"1196_CR36","doi-asserted-by":"publisher","first-page":"2018","DOI":"10.1007\/s00453-021-00817-8","volume":"83","author":"AL Konstantinidis","year":"2021","unstructured":"Konstantinidis, A.L., Papadopoulos, C.: Cluster deletion on interval graphs and split related graphs. Algorithmica 83(7), 2018\u20132046 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00817-8","journal-title":"Algorithmica"},{"issue":"2","key":"1196_CR37","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/0890-5401(87)90028-9","volume":"74","author":"D Kratsch","year":"1987","unstructured":"Kratsch, D.: Finding the minimum bandwidth of an interval graphs. Inf. Comput. 74(2), 140\u2013158 (1987). https:\/\/doi.org\/10.1016\/0890-5401(87)90028-9","journal-title":"Inf. Comput."},{"issue":"4","key":"1196_CR38","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1137\/S0895480199359624","volume":"15","author":"D Kratsch","year":"2002","unstructured":"Kratsch, D., Stewart, L.: Approximating bandwidth by mixing layouts of interval graphs. SIAM J. Discret. Math. 15(4), 435\u2013449 (2002). https:\/\/doi.org\/10.1137\/S0895480199359624","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1196_CR39","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C Lekkeikerker","year":"1962","unstructured":"Lekkeikerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundam. Math. 51(1), 45\u201364 (1962)","journal-title":"Fundam. Math."},{"issue":"1","key":"1196_CR40","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7151\/dmgt.1061","volume":"18","author":"I-J Lin","year":"1998","unstructured":"Lin, I.-J., McKee, T.A., West, D.B.: The leafage of a chordal graph. Discuss. Math. Graph Theory 18(1), 23\u201348 (1998). https:\/\/doi.org\/10.7151\/dmgt.1061","journal-title":"Discuss. Math. Graph Theory"},{"issue":"2","key":"1196_CR41","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"GS Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. ACM 26(2), 183\u2013195 (1979). https:\/\/doi.org\/10.1145\/322123.322125","journal-title":"J. ACM"},{"issue":"3","key":"1196_CR42","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.10.007","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1196_CR43","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/110855247","volume":"43","author":"D Marx","year":"2014","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. 43(2), 355\u2013388 (2014). https:\/\/doi.org\/10.1137\/110855247","journal-title":"SIAM J. Comput."},{"key":"1196_CR44","doi-asserted-by":"publisher","unstructured":"Misra, P., Panolan, F., Rai, A., Saurabh, S., Sharma, R.: Quick separation in chordal and split graphs. In: Javier, E., Daniel, K. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Prague, Czech Republic, volume 170 of LIPIcs, pp. 70:1\u201370:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.70","DOI":"10.4230\/LIPIcs.MFCS.2020.70"},{"issue":"12","key":"1196_CR45","doi-asserted-by":"publisher","first-page":"1791","DOI":"10.1016\/j.dam.2012.03.021","volume":"160","author":"C Papadopoulos","year":"2012","unstructured":"Papadopoulos, C.: Restricted vertex multicut on permutation graphs. Discret. Appl. Math. 160(12), 1791\u20131797 (2012). https:\/\/doi.org\/10.1016\/j.dam.2012.03.021","journal-title":"Discret. Appl. Math."},{"key":"1196_CR46","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.dam.2018.11.017","volume":"258","author":"C Papadopoulos","year":"2019","unstructured":"Papadopoulos, C., Tzimas, S.: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. Discret. Appl. Math. 258, 204\u2013221 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.11.017","journal-title":"Discret. Appl. Math."},{"key":"1196_CR47","doi-asserted-by":"publisher","unstructured":"Papadopoulos, C., haris, Tzimas, Spyridon: Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage. In Cristina Bazgan and Henning Fernau, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, volume 13270 of Lecture Notes in Computer Science, pp. 466\u2013479. Springer, (2022). https:\/\/doi.org\/10.1007\/978-3-031-06678-8_34","DOI":"10.1007\/978-3-031-06678-8_34"},{"key":"1196_CR48","volume-title":"Representations of Rigid Cycle Graphs","author":"JR Walter","year":"1972","unstructured":"Walter, J.R.: Representations of Rigid Cycle Graphs. Wayne State University, Detroit (1972)"},{"issue":"1","key":"1196_CR49","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/net.3230150109","volume":"15","author":"K White","year":"1985","unstructured":"White, K., Farber, M., Pulleyblank, W.R.: Steiner trees, connected domination and strongly chordal graphs. Networks 15(1), 109\u2013124 (1985). https:\/\/doi.org\/10.1002\/net.3230150109","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01196-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01196-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01196-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T03:02:25Z","timestamp":1713668545000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01196-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,29]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1196"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01196-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,29]]},"assertion":[{"value":"5 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 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 have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}