{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T06:05:05Z","timestamp":1773727505162,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T00:00:00Z","timestamp":1773705600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T00:00:00Z","timestamp":1773705600000},"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":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00453-026-01374-8","type":"journal-article","created":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T04:23:30Z","timestamp":1773721410000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed-Parameter Tractable"],"prefix":"10.1007","volume":"88","author":[{"given":"Vikraman","family":"Arvind","sequence":"first","affiliation":[]},{"given":"Roman","family":"Nedela","sequence":"additional","affiliation":[]},{"given":"Ilia","family":"Ponomarenko","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Zeman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,17]]},"reference":[{"key":"1374_CR1","unstructured":"Agaoglu, D., Hlinen\u00fd, P.: Isomorphism problem for $$S_d$$-graphs. In: Esparza, J., Kr\u00e1l\u2019, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24\u201328, 2020, Prague, Czech Republic. LIPIcs, vol. 170, pp. 4:1\u20134:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1374_CR2","unstructured":"Agaoglu, D., Hlinen\u00fd, P.: Isomorphism testing for $$T$$-graphs in FPT. CoRR arXiv: 2111.10910 (2021)"},{"issue":"1","key":"1374_CR3","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s00453-013-9787-y","volume":"71","author":"V Arvind","year":"2015","unstructured":"Arvind, V., Das, B., K\u00f6bler, J., Toda, S.: Colored hypergraph isomorphism is fixed parameter tractable. Algorithmica 71(1), 120\u2013138 (2015). https:\/\/doi.org\/10.1007\/s00453-013-9787-y","journal-title":"Algorithmica"},{"key":"1374_CR4","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 (extended abstract). In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, T\u00fcbingen, Germany, June 22\u201324, 2022, Revised Selected Papers. Lecture Notes in Computer Science, vol. 13453, pp. 29\u201342. Springer (2022)","DOI":"10.1007\/978-3-031-15914-5_3"},{"key":"1374_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016. pp. 684\u2013697. ACM (2016)","DOI":"10.1145\/2897518.2897542"},{"issue":"1\u20133","key":"1374_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Biro","year":"1992","unstructured":"Biro, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Discret. Math. 100(1\u20133), 267\u2013279 (1992)","journal-title":"Discret. Math."},{"issue":"4","key":"1374_CR7","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"HL Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms 11(4), 631\u2013643 (1990). https:\/\/doi.org\/10.1016\/0196-6774(90)90013-5","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"1374_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0012-365X(89)90162-3","volume":"78","author":"N Brand","year":"1989","unstructured":"Brand, N.: Isomorphisms of cyclic combinatorial objects. Discret. Math. 78(1\u20132), 73\u201381 (1989)","journal-title":"Discret. Math."},{"key":"1374_CR9","doi-asserted-by":"crossref","unstructured":"\u00c7agirici, D.A., Hlinen\u00fd, P.: Isomorphism testing for $$T$$-graphs in FPT. In: Mutzel, P., Rahman, M.S., Slamin (eds.) WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24\u201326, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13174, pp. 239\u2013250. Springer (2022)","DOI":"10.1007\/978-3-030-96731-4_20"},{"issue":"2","key":"1374_CR10","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/s00453-022-01033-8","volume":"85","author":"DA \u00c7agirici","year":"2023","unstructured":"\u00c7agirici, D.A., Hlinen\u00fd, P.: Efficient isomorphism for $$S_d$$-graphs and $$T$$-graphs. Algorithmica 85(2), 352\u2013383 (2023)","journal-title":"Algorithmica"},{"key":"1374_CR11","unstructured":"\u00c7agirici, D.A., Zeman, P.: Recognition and isomorphism of proper u-graphs in fpt-time. CoRR arXiv:2206.13372 (2022)"},{"key":"1374_CR12","doi-asserted-by":"crossref","unstructured":"Chaplick, S., T\u00f6pfer, M., Voborn\u00edk, J., Zeman, P.: On $$H$$-topological intersection graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21\u201323, 2017, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10520, pp. 167\u2013179. Springer (2017)","DOI":"10.1007\/978-3-319-68705-6_13"},{"key":"1374_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.endm.2017.06.042","volume":"61","author":"S Chaplick","year":"2017","unstructured":"Chaplick, S., Zeman, P.: Combinatorial problems on $$H$$-graphs. Electron. Notes Discret. Math. 61, 223\u2013229 (2017)","journal-title":"Electron. Notes Discret. Math."},{"key":"1374_CR14","volume-title":"Coherent Configurations","author":"G Chen","year":"2019","unstructured":"Chen, G., Ponomarenko, I.: Coherent Configurations. Central China Normal University Press, Wuhan (2019). (http:\/\/www.pdmi.ras.ru\/\u00a0inp\/ccNOTES.pdf)"},{"issue":"1","key":"1374_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0210015","volume":"10","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn, C.J., Booth, K.S.: Linear times automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10(1), 203\u2013225 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"1374_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0012-365X(00)00152-7","volume":"225","author":"S Evdokimov","year":"2000","unstructured":"Evdokimov, S., Ponomarenko, I., Tinhofer, G.: Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discret. Math. 225(1\u20133), 149\u2013172 (2000)","journal-title":"Discret. Math."},{"key":"1374_CR17","doi-asserted-by":"publisher","unstructured":"Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus (working paper). In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980). pp. 236\u2013243. ACM (1980) https:\/\/doi.org\/10.1145\/800141.804671","DOI":"10.1145\/800141.804671"},{"issue":"9","key":"1374_CR18","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.: On the tractability of optimization problems on $$H$$-graphs. Algorithmica 82(9), 2432\u20132473 (2020)","journal-title":"Algorithmica"},{"issue":"5","key":"1374_CR19","doi-asserted-by":"publisher","first-page":"1428","DOI":"10.1007\/s00453-023-01196-y","volume":"86","author":"E Galby","year":"2024","unstructured":"Galby, E., Marx, D., Schepper, P., Sharma, R., Tale, P.: Domination and cut problems on chordal graphs with bounded leafage. Algorithmica 86(5), 1428\u20131474 (2024)","journal-title":"Algorithmica"},{"issue":"1","key":"1374_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Ser. B. 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory, Ser. B."},{"issue":"6","key":"1374_CR21","doi-asserted-by":"publisher","first-page":"S18\u20131","DOI":"10.1137\/19M1245293","volume":"52","author":"M Grohe","year":"2023","unstructured":"Grohe, M., Neuen, D., Schweitzer, P.: A faster isomorphism test for graphs of small degree. SIAM J. Comput. 52(6), S18-1-S18-215 (2023)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1374_CR22","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/3382082","volume":"16","author":"M Grohe","year":"2020","unstructured":"Grohe, M., Neuen, D., Schweitzer, P., Wiebking, D.: An improved isomorphism test for bounded-tree-width graphs. ACM Trans. Algorithms 16(3), 34:1-34:31 (2020). https:\/\/doi.org\/10.1145\/3382082","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1374_CR23","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1137\/21M1401930","volume":"52","author":"M Grohe","year":"2023","unstructured":"Grohe, M., Neuen, D., Wiebking, D.: Isomorphism testing for graphs excluding small minors. SIAM J. Comput. 52(1), 238\u2013272 (2023). https:\/\/doi.org\/10.1137\/21M1401930","journal-title":"SIAM J. Comput."},{"key":"1374_CR24","doi-asserted-by":"crossref","unstructured":"Habib, M., Stacho, J.: Polynomial-time algorithm for the leafage of chordal graphs. In: Fiat, A., Sanders, P. (eds.) Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7\u20139, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5757, pp. 290\u2013300. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_27"},{"issue":"1","key":"1374_CR25","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7151\/dmgt.1061","volume":"18","author":"I Lin","year":"1998","unstructured":"Lin, I., McKee, T.A., West, D.B.: The leafage of a chordal graph. Discuss. Math. Graph Theory 18(1), 23\u201348 (1998)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"1","key":"1374_CR26","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1137\/140999980","volume":"46","author":"D Lokshtanov","year":"2017","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM J. Comput. 46(1), 161\u2013189 (2017)","journal-title":"SIAM J. Comput."},{"key":"1374_CR27","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. In: Leonardi, S., Gupta, A. (eds.) STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20\u201324, 2022. pp. 914\u2013923. ACM (2022)","DOI":"10.1145\/3519935.3520076"},{"issue":"2","key":"1374_CR28","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)","journal-title":"J. ACM"},{"issue":"1","key":"1374_CR29","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"1374_CR30","doi-asserted-by":"crossref","unstructured":"Luks, E.M.: Permutation groups and polynomial-time computation. In: Groups And Computation, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 7\u201310, 1991. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 11, pp. 139\u2013175. DIMACS\/AMS (1991). https:\/\/doi.org\/10.1090\/dimacs\/011\/11","DOI":"10.1090\/dimacs\/011\/11"},{"issue":"3","key":"1374_CR31","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/3527667","volume":"18","author":"D Neuen","year":"2022","unstructured":"Neuen, D.: Hypergraph isomorphism for groups with restricted composition factors. ACM Trans. Algorithms 18(3), 27:1-27:50 (2022). https:\/\/doi.org\/10.1145\/3527667","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1374_CR32","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1137\/22M1514076","volume":"38","author":"D Neuen","year":"2024","unstructured":"Neuen, D.: Isomorphism testing parameterized by genus and beyond. SIAM J. Discret. Math. 38(1), 453\u2013484 (2024)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"1374_CR33","doi-asserted-by":"publisher","first-page":"1621","DOI":"10.1007\/BF01098279","volume":"55","author":"I Ponomarenko","year":"1991","unstructured":"Ponomarenko, I.: The isomorphism problem for classes of graphs closed under contraction. J. Sov. Math. 55(2), 1621\u20131643 (1991)","journal-title":"J. Sov. Math."},{"key":"1374_CR34","doi-asserted-by":"crossref","unstructured":"Schweitzer, P., Wiebking, D.: A unifying method for the design of algorithms canonizing combinatorial objects. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23\u201326, 2019. pp. 1247\u20131258. ACM (2019)","DOI":"10.1145\/3313276.3316338"},{"key":"1374_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546549","volume-title":"Permutation group algorithms","author":"\u00c1 Seress","year":"2003","unstructured":"Seress, \u00c1.: Permutation group algorithms, vol. 152. Cambridge University Press (2003)"},{"key":"1374_CR36","doi-asserted-by":"crossref","unstructured":"Stacho, J.: On 2-subcolourings of chordal graphs. In: Laber, E.S., Bornstein, C.F., Nogueira, L.T., Faria, L. (eds.) LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, B\u00fazios, Brazil, April 7\u201311, 2008, Proceedings. Lecture Notes in Computer Science, vol. 4957, pp. 544\u2013554. Springer (2008)","DOI":"10.1007\/978-3-540-78773-0_47"},{"key":"1374_CR37","unstructured":"Weisfeiler, B., Leman, A.: The reduction of a graph to canonical form and the algebra which appears therein. NTI Series 2, 12\u201316 (1968), https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf, The url links to an English translation"},{"key":"1374_CR38","unstructured":"Wiebking, D.: Graph isomorphism in quasipolynomial time parameterized by treewidth. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, Saarbr\u00fccken, Germany (Virtual Conference), July 8\u201311, 2020. LIPIcs, vol. 168, pp. 103:1\u2013103:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.103"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01374-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01374-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01374-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T04:23:35Z","timestamp":1773721415000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01374-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,17]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1374"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01374-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,17]]},"assertion":[{"value":"1 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2026","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 declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"29"}}