{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T15:50:57Z","timestamp":1773762657352,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001824","name":"grantov\u00e1 agentura cesk\u00e9 republiky","doi-asserted-by":"publisher","award":["20-04567S"],"award-info":[{"award-number":["20-04567S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s00453-022-01033-8","type":"journal-article","created":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T08:04:10Z","timestamp":1662365050000},"page":"352-383","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Isomorphism for $$S_d$$-Graphs and T-Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Deniz","family":"A\u011fao\u011flu \u00c7a\u011f\u0131r\u0131c\u0131","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2125-1514","authenticated-orcid":false,"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,5]]},"reference":[{"key":"1033_CR1","doi-asserted-by":"publisher","unstructured":"A\u011fao\u011flu \u00c7a\u011f\u0131r\u0131c\u0131, D., Hlin\u011bn\u00fd, P.: Isomorphism testing for t-graphs in FPT. In WALCOM, Volume 13174 of Lecture Notes in Computer Science, pp. 239\u2013250. Springer (2022). arXiv:2111.10910, https:\/\/doi.org\/10.1007\/978-3-030-96731-4_20","DOI":"10.1007\/978-3-030-96731-4_20"},{"key":"1033_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1974)"},{"key":"1033_CR3","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. Accepted to WG\u00a02022. arXiv:2107.10689 (2021)","DOI":"10.1007\/978-3-031-15914-5_3"},{"key":"1033_CR4","unstructured":"Babai, L.: Monte Carlo algorithms in graph isomorphism testing. Technical\u00a0Report\u00a079-10, Universit\u00e9 de Montr\u00e9al (1979)"},{"key":"1033_CR5","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/2897518.2897542","DOI":"10.1145\/2897518.2897542"},{"key":"1033_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Discrete Math. 100, 267\u2013279 (1992)","journal-title":"Discrete Math."},{"issue":"3","key":"1033_CR7","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"key":"1033_CR8","doi-asserted-by":"publisher","unstructured":"Bouland, A., Dawar, A., Kopczy\u0144ski, E.: On tractable parameterizations of graph isomorphism. In: Thilikos, D.M., Woeginger, G.J. (eds) Parameterized and exact computation. In: 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12\u201314 (2012). Proceedings, Volume 7535 of Lecture Notes in Computer Science, pp. 218\u2013230. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_21","DOI":"10.1007\/978-3-642-33293-7_21"},{"key":"1033_CR9","doi-asserted-by":"publisher","unstructured":"Chaplick, S., Golovach, P.A., Hartmann, T.A., Knop, D.: Recognizing proper tree-graphs. In: Cao, Y., Pilipczuk, M. (eds.) 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14\u201318, 2020, Hong Kong, China (Virtual Conference), Volume 180 of LIPIcs, pp. 8:1\u20138:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.8","DOI":"10.4230\/LIPIcs.IPEC.2020.8"},{"key":"1033_CR10","doi-asserted-by":"publisher","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\u201343rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21\u201323, 2017, Revised Selected Papers, Volume 10520 of Lecture Notes in Computer Science, pp. 167\u2013179. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_13.","DOI":"10.1007\/978-3-319-68705-6_13."},{"key":"1033_CR11","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 Discrete Math. 61, 223\u2013229 (2017). https:\/\/doi.org\/10.1016\/j.endm.2017.06.042","journal-title":"Electron. Notes Discrete Math."},{"key":"1033_CR12","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1137\/0606026","volume":"6","author":"FRK Chung","year":"1985","unstructured":"Chung, F.R.K.: On the cutwidth and the topological bandwidth of a tree. SIAM J. Algebr. Discrete Methods 6, 268\u2013277 (1985)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"1","key":"1033_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11(1), 13\u201321 (1981). https:\/\/doi.org\/10.1002\/net.3230110103","journal-title":"Networks"},{"issue":"3","key":"1033_CR14","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s004930050059","volume":"19","author":"S Evdokimov","year":"1999","unstructured":"Evdokimov, S., Ponomarenko, I.N.: Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks. Combinatorica 19(3), 321\u2013333 (1999). https:\/\/doi.org\/10.1007\/s004930050059","journal-title":"Combinatorica"},{"key":"1033_CR15","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-1-4612-3086-1_3","volume-title":"Mathematical Foundations of Computer Science","author":"PA Fejer","year":"1991","unstructured":"Fejer, P.A., Simovici, D.A.: Partially ordered sets. In: Mathematical Foundations of Computer Science. Texts and Monographs in Computer Science, pp. 127\u2013175. Springer, New York (1991)"},{"key":"1033_CR16","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.-F.: On the tractability of optimization problems on H-graphs. In: Azar, Y., Bast, H., Herman, G. (eds) 26th Annual European Symposium on Algorithms, ESA 2018, August 20\u201322, 2018, Helsinki, Finland, Volume 112 of LIPIcs, pp. 30:1\u201330:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.30","DOI":"10.4230\/LIPIcs.ESA.2018.30"},{"key":"1033_CR17","doi-asserted-by":"publisher","unstructured":"Furst, M.L., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pp. 36\u201341. IEEE Computer Society (1980). https:\/\/doi.org\/10.1109\/SFCS.1980.34","DOI":"10.1109\/SFCS.1980.34"},{"key":"1033_CR18","unstructured":"Furst, M.L., Hopcroft, J.E., Luks, Eugene\u00a0M.: A subexponential algorithm for trivalent graph isomorphism. In: Proceedings of 11th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congressum Numerantium 3 (1980)"},{"issue":"1","key":"1033_CR19","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). https:\/\/doi.org\/10.1016\/0095-8956(74)90094-X","journal-title":"J. Comb. Theory Ser. B"},{"key":"1033_CR20","doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs (preliminary report). In: Constable, R.L., Ritchie, R.W., Carlyle, J.W., Harrison, M.A. (eds) Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30\u2013May 2, 1974, Seattle, Washington, USA, pp. 172\u2013184. ACM (1974) https:\/\/doi.org\/10.1145\/800119.803896","DOI":"10.1145\/800119.803896"},{"key":"1033_CR21","unstructured":"Kawarabayashi, K.: Graph isomorphism for bounded genus graphs in linear time. CoRR. arXiv:1511.02460 (2015)"},{"key":"1033_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.tcs.2015.02.007","volume":"576","author":"P Klav\u00edk","year":"2015","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Otachi, Y., Saitoh, T.: Extending partial representations of subclasses of chordal graphs. Theor. Comput. Sci. 576, 85\u2013101 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.02.007","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1033_CR23","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). https:\/\/doi.org\/10.1137\/140999980","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1033_CR24","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). https:\/\/doi.org\/10.1016\/0022-0000(82)90009-5","journal-title":"J. Comput. Syst. Sci."},{"key":"1033_CR25","series-title":"Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719802","volume-title":"Topics in Intersection Graph Theory","author":"TA McKee","year":"1999","unstructured":"McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory. Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1999)"},{"key":"1033_CR26","doi-asserted-by":"publisher","unstructured":"Miller, G.L.: Isomorphism testing for graphs of bounded genus. In: Miller, R.E., Ginsburg, S., Burkhard, W.A., Lipton, R.J. (eds) Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28\u201330, 1980, Los Angeles, California, USA, pp. 225\u2013235. ACM (1980). https:\/\/doi.org\/10.1145\/800141.804670","DOI":"10.1145\/800141.804670"},{"key":"1033_CR27","doi-asserted-by":"publisher","unstructured":"Neuen, D.: Isomorphism testing parameterized by genus and beyond. In: Mutzel, P., Pagh, R., Herman, G. (eds) 29th Annual European Symposium on Algorithms, ESA 2021, September 6\u20138, 2021, Lisbon, Portugal (Virtual Conference), Volume 204 of LIPIcs, pp. 72:1\u201372:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.72.","DOI":"10.4230\/LIPIcs.ESA.2021.72."},{"issue":"2","key":"1033_CR28","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1033_CR29","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.dam.2004.06.008","volume":"145","author":"R Uehara","year":"2005","unstructured":"Uehara, R., Toda, S., Nagoya, T.: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. Discrete Appl. Math. 145(3), 479\u2013482 (2005). https:\/\/doi.org\/10.1016\/j.dam.2004.06.008","journal-title":"Discrete Appl. Math."},{"key":"1033_CR30","doi-asserted-by":"publisher","first-page":"1426","DOI":"10.1007\/BF02104746","volume":"29","author":"VN Zemlyachenko","year":"1985","unstructured":"Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. J. Sov. Math. 29, 1426\u20131481 (1985)","journal-title":"J. Sov. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01033-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01033-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01033-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T09:17:34Z","timestamp":1674811054000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01033-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,5]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1033"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01033-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,5]]},"assertion":[{"value":"12 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}