{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T23:24:37Z","timestamp":1744932277634,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,12,4]],"date-time":"2022-12-04T00:00:00Z","timestamp":1670112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,4]],"date-time":"2022-12-04T00:00:00Z","timestamp":1670112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704","714704","714704","714704"],"award-info":[{"award-number":["714704","714704","714704","714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The notion of<jats:italic>forbidden-transition graphs<\/jats:italic>allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is<jats:italic>permitted<\/jats:italic>or<jats:italic>forbidden<\/jats:italic>; a walk is<jats:italic>compatible<\/jats:italic>if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is<jats:italic>W<\/jats:italic>[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting.<\/jats:p>","DOI":"10.1007\/s00453-022-01064-1","type":"journal-article","created":{"date-parts":[[2022,12,4]],"date-time":"2022-12-04T07:02:45Z","timestamp":1670137365000},"page":"1202-1250","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Thomas","family":"Bellitto","sequence":"first","affiliation":[]},{"given":"Shaohua","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1414-3507","authenticated-orcid":false,"given":"Karolina","family":"Okrasa","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,4]]},"reference":[{"issue":"3","key":"1064_CR1","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/j.tcs.2008.09.021","volume":"409","author":"A Abouelaoualim","year":"2008","unstructured":"Abouelaoualim, A., Das, K.C., Faria, L., Manoussakis, Y., Martinhon, C.A.J., Saad, R.: Paths and trails in edge-colored graphs. Theor. Comput. Sci. 409(3), 497\u2013510 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"1064_CR2","unstructured":"Ahmed, M., Lubiw, A.: Shortest paths avoiding forbidden subpaths. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp. 63\u201374, (2009)"},{"key":"1064_CR3","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2020.01.012","volume":"814","author":"J Bang-Jensen","year":"2020","unstructured":"Bang-Jensen, J., Bellitto, T., Lochet, W., Yeo, A.: The directed 2-linkage problem with length constraints. Theoret. Comput. Sci. 814, 69\u201373 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"1064_CR4","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Bellitto, T., Yeo, A.: Supereulerian 2-edge-coloured graphs. Technical report, arXiv:2004.01955 [math.CO], (2020)","DOI":"10.1007\/s00373-021-02377-8"},{"key":"1064_CR5","volume-title":"Digraphs - Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs - Theory, Algorithms and Applications. Springer, Berlin (2009)"},{"key":"1064_CR6","doi-asserted-by":"crossref","unstructured":"Bellitto, T.: Separating codes and traffic monitoring. Theoretical Computer Science, Selected papers presented at the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM 2016) vol. 717, pp. 73\u201385 (2018)","DOI":"10.1016\/j.tcs.2017.03.044"},{"key":"1064_CR7","doi-asserted-by":"crossref","unstructured":"Bellitto, T., Bergougnoux, B.: On minimum connecting transition sets in graphs. In Brandst\u00e4dt, A., K\u00f6hler, E., Meer, K. (eds.) Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), volume 11159 of Lecture Notes in Computer Science, pp. 40\u201351. Springer (2018)","DOI":"10.1007\/978-3-030-00256-5_4"},{"key":"1064_CR8","unstructured":"Bentert, M., Nichterlein, A., Renken, M., Zschoche, P.: Using a geometric lens to find k disjoint shortest paths. In Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 26:1\u201326:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"1064_CR9","unstructured":"B\u00e9rczi, K., Kobayashi, Y.: The directed disjoint shortest paths problem. In Pruhs, K., Sohler, C. (eds.) Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017), volume\u00a087 of LIPIcs, pp. 13:1\u201313:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"issue":"4","key":"1064_CR10","doi-asserted-by":"publisher","first-page":"2326","DOI":"10.1137\/17M1148566","volume":"33","author":"I Bez\u00e1kov\u00e1","year":"2019","unstructured":"Bez\u00e1kov\u00e1, I., Curticapean, R., Dell, H., Fomin, F.V.: Finding detours is fixed-parameter tractable. SIAM J. Discret. Math. 33(4), 2326\u20132345 (2019)","journal-title":"SIAM J. Discret. Math."},{"key":"1064_CR11","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)","journal-title":"Inf. Comput."},{"key":"1064_CR12","doi-asserted-by":"crossref","unstructured":"Brand, C., Ceylan, E., Ganian, R., Hatschka, C., Korchemna, V.: Edge-cut width: An algorithmically driven analogue of\u00a0treewidth based on\u00a0edge cuts. In Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, pp. 98\u2013113. Springer, Berlin (2022)","DOI":"10.1007\/978-3-031-15914-5_8"},{"key":"1064_CR13","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.dam.2017.04.033","volume":"229","author":"A Contreras-Balbuena","year":"2017","unstructured":"Contreras-Balbuena, A., Galeana-S\u00e1nchez, H., Goldfeder, I.A.: A new sufficient condition for the existence of alternating hamiltonian cycles in 2-edge-colored multigraphs. Discret. Appl. Math. 229, 55\u201363 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1064_CR14","unstructured":"Contreras-Balbuena, A., Galeana-S\u00e1nchez, H., Goldfeder, I.\u00a0A.: Alternating hamiltonian cycles in 2-edge-colored multigraphs. Discrete Math. Theor. Comput. Sci., 21(1), (2019)"},{"key":"1064_CR15","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, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"2","key":"1064_CR16","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0166-218X(92)00171-H","volume":"50","author":"D Dorninger","year":"1994","unstructured":"Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discret. Appl. Math. 50(2), 159\u2013168 (1994)","journal-title":"Discret. Appl. Math."},{"key":"1064_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"issue":"1","key":"1064_CR18","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.disc.2007.12.050","volume":"309","author":"Z Dvor\u00e1k","year":"2009","unstructured":"Dvor\u00e1k, Z.: Two-factors in orientated graphs with forbidden transitions. Discret. Math. 309(1), 104\u2013112 (2009)","journal-title":"Discret. Math."},{"key":"1064_CR19","unstructured":"Eiben, E., Ganian, R., Hamm, T., Jaffke, L., Kwon, O.-J.: A unifying framework for characterizing and computing width measures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 63:1\u201363:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"1","key":"1064_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1064_CR21","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"key":"1064_CR22","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"1064_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"1064_CR24","doi-asserted-by":"crossref","unstructured":"Ganian, R., Kim, E.\u00a0J., Szeider, S.: Algorithmic applications of tree-cut width. In Italiano, G.F., Pighizzini, G., Sannella, D. (eds.) Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), volume 9235 of Lecture Notes in Computer Science, pp. 348\u2013360. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48054-0_29"},{"key":"1064_CR25","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ordyniak, S.: The power of cut-based parameters for computing edge disjoint paths. In International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 190\u2013204. Springer, Berlin (2019)","DOI":"10.1007\/978-3-030-30786-8_15"},{"issue":"1","key":"1064_CR26","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.orl.2018.11.011","volume":"47","author":"M Gottschau","year":"2019","unstructured":"Gottschau, M., Kaiser, M., Waldmann, C.: The undirected two disjoint shortest paths problem. Oper. Res. Lett. 47(1), 70\u201375 (2019)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"1064_CR27","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.dam.2012.10.025","volume":"161","author":"L Gourv\u00e8s","year":"2013","unstructured":"Gourv\u00e8s, L., Lyra, A., Martinhon, C.A.J., Monnot, J.: Complexity of trails, paths and circuits in arc-colored digraphs. Discret. Appl. Math. 161(6), 819\u2013828 (2013)","journal-title":"Discret. Appl. Math."},{"key":"1064_CR28","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.endm.2009.11.037","volume":"35","author":"L Gourv\u00e8s","year":"2009","unstructured":"Gourv\u00e8s, L., Lyra, A., Martinhon, C.A.J., Monnot, J., Protti, F.: On s-t paths and trails in edge-colored graphs. Electr. Notes Discrete Math. 35, 221\u2013226 (2009)","journal-title":"Electr. Notes Discrete Math."},{"issue":"1","key":"1064_CR29","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0095-8956(83)90008-4","volume":"34","author":"JW Grossman","year":"1983","unstructured":"Grossman, J.W., H\u00e4ggkvist, R.: Alternating cycles in edge-partitioned graphs. J. Comb. Theory Ser. B 34(1), 77\u201381 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1064_CR30","doi-asserted-by":"crossref","unstructured":"Gutin, G., Kim, E.\u00a0J.: Properly coloured cycles and paths: results and open problems. In Graph Theory, Computational Intelligence and Thought, Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday, pp. 200\u2013208, (2009)","DOI":"10.1007\/978-3-642-02029-2_19"},{"key":"1064_CR31","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.dam.2016.08.005","volume":"217","author":"GZ Gutin","year":"2017","unstructured":"Gutin, G.Z., Jones, M., Sheng, B., Wahlstr\u00f6m, M., Yeo, A.: Chinese postman problem on edge-colored multigraphs. Discret. Appl. Math. 217, 196\u2013202 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1064_CR32","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of $$k$$-SAT. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC 1999), pp. 237\u2013240, (1999)"},{"key":"1064_CR33","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 653\u2013662 (1998)","DOI":"10.1109\/SFCS.1998.743516"},{"key":"1064_CR34","doi-asserted-by":"crossref","unstructured":"Kant\u00e9, M.M., Laforest, C., Mom\u00e8ge, B.: Trees in graphs with conflict edges or forbidden transitions. In Chan, T.H., Lau, L.C., Trevisan, L. (eds.) Proceedins of the 10th International Conference on Theory and Applications of Models of Computation (TAMC 2013), volume 7876 of Lecture Notes in Computer Science, pp. 343\u2013354. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38236-9_31"},{"key":"1064_CR35","doi-asserted-by":"crossref","unstructured":"Kant\u00e9, M.M., Moataz, F.Z., Mom\u00e8ge, B., Nisse, N.: Finding paths in grids with forbidden transitions. In Mayr, E.W. (ed.) Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), volume 9224 of Lecture Notes in Computer Science, pp. 154\u2013168. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-53174-7_12"},{"issue":"1","key":"1064_CR36","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00453-016-0245-5","volume":"80","author":"EJ Kim","year":"2018","unstructured":"Kim, E.J., Oum, S.-I., Paul, C., Sau, I., Thilikos, D.M.: An fpt 2-approximation for tree-cut decomposition. Algorithmica 80(1), 116\u2013135 (2018)","journal-title":"Algorithmica"},{"issue":"1","key":"1064_CR37","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.orl.2018.11.012","volume":"47","author":"Y Kobayashi","year":"2019","unstructured":"Kobayashi, Y., Sako, R.: Two disjoint shortest paths problem with non-negative edge length. Oper. Res. Lett. 47(1), 66\u201369 (2019)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1064_CR38","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jda.2010.07.003","volume":"9","author":"C Komusiewicz","year":"2011","unstructured":"Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Deconstructing intractability-a multivariate complexity analysis of interval constrained coloring. J. Discrete Algorithms 9(1), 137\u2013151 (2011)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"1064_CR39","first-page":"76","volume":"18","author":"A Kotzig","year":"1968","unstructured":"Kotzig, A.: Moves without forbidden transitions in a graph. Matematick\u00fd \u010dasopis 18(1), 76\u201380 (1968)","journal-title":"Matematick\u00fd \u010dasopis"},{"issue":"6","key":"1064_CR40","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1016\/j.disc.2017.01.023","volume":"340","author":"R Li","year":"2017","unstructured":"Li, R., Broersma, H., Xu, C., Zhang, S.: Cycle extension in edge-colored complete graphs. Discret. Math. 340(6), 1235\u20131241 (2017)","journal-title":"Discret. Math."},{"issue":"1","key":"1064_CR41","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s00373-018-1989-2","volume":"35","author":"R Li","year":"2019","unstructured":"Li, R., Broersma, H., Zhang, S.: Properly edge-colored theta graphs in edge-colored complete graphs. Graphs Comb. 35(1), 261\u2013286 (2019)","journal-title":"Graphs Comb."},{"key":"1064_CR42","doi-asserted-by":"crossref","unstructured":"Lochet, W.: A polynomial time algorithm for the k-disjoint shortest paths problem. In Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 169\u2013178. SIAM","DOI":"10.1137\/1.9781611976465.12"},{"issue":"1","key":"1064_CR43","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."},{"issue":"1","key":"1064_CR44","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/130924056","volume":"28","author":"D Marx","year":"2014","unstructured":"Marx, D., Wollan, P.: Immersions in highly edge connected graphs. SIAM J. Discret. Math. 28(1), 503\u2013520 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"1064_CR45","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201995), pp. 182\u2013191 (1995)"},{"key":"1064_CR46","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"1","key":"1064_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/322047.322048","volume":"25","author":"Y Perl","year":"1978","unstructured":"Perl, Y., Shiloach, Y.: Finding two disjoint paths between two pairs of vertices in a graph. J. ACM 25(1), 1\u20139 (1978)","journal-title":"J. ACM"},{"issue":"1","key":"1064_CR48","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2\u20133","key":"1064_CR49","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0166-218X(02)00251-2","volume":"126","author":"S Szeider","year":"2003","unstructured":"Szeider, S.: Finding paths in graphs avoiding forbidden transitions. Discret. Appl. Math. 126(2\u20133), 261\u2013273 (2003)","journal-title":"Discret. Appl. Math."},{"key":"1064_CR50","unstructured":"Weller, M., Sorge, M., Contributors: The Graph Parameter Hierarchy. Accessed (October 2022)"},{"key":"1064_CR51","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2014.07.003","volume":"110","author":"P Wollan","year":"2015","unstructured":"Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47\u201366 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"1064_CR52","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jctb.1997.1728","volume":"69","author":"A Yeo","year":"1997","unstructured":"Yeo, A.: A note on alternating cycles in edge-coloured graphs. J. Comb. Theory Ser. B 69(2), 222\u2013225 (1997)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1064_CR53","first-page":"2.7:1","volume":"24","author":"M Ziobro","year":"2019","unstructured":"Ziobro, M., Pilipczuk, M.: Finding hamiltonian cycle in graphs of bounded treewidth: experimental evaluation. ACM J. Exp. Algorithmics 24(1), 2.7:1-2.7:18 (2019)","journal-title":"ACM J. Exp. Algorithmics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01064-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01064-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01064-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T22:19:15Z","timestamp":1728512355000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01064-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,4]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1064"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01064-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,12,4]]},"assertion":[{"value":"2 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}