{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T00:33:59Z","timestamp":1701131639144},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"S2","license":[{"start":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T00:00:00Z","timestamp":1663718400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T00:00:00Z","timestamp":1663718400000},"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":["Combinatorica"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00493-021-4736-x","type":"journal-article","created":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T17:03:23Z","timestamp":1663779803000},"page":"1253-1282","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding a Shortest Non-Zero Path in Group-Labeled Graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Yoichi","family":"Iwata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yutaro","family":"Yamaguchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,21]]},"reference":[{"key":"4736_CR1","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.1137\/120864271","volume":"42","author":"S Cabello","year":"2013","unstructured":"S. Cabello, E. W. Chambers and J. Erickson: Multiple-source shortest paths in embedded graphs, SIAM Journal on Computing 42 (2013), 1542\u20131571.","journal-title":"SIAM Journal on Computing"},{"key":"4736_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s00493-008-2157-8","volume":"28","author":"M Chudnovsky","year":"2008","unstructured":"M. Chudnovsky, W. H. Cunningham and J. Geelen: An algorithm for packing non-zero A-paths in group-labelled graphs, Combinatorica 28 (2008), 145\u2013161.","journal-title":"Combinatorica"},{"key":"4736_CR3","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00493-006-0030-1","volume":"26","author":"M Chudnovsky","year":"2006","unstructured":"M. Chudnovsky, J. Geelen, B. Gerards, L. Goddyn, M. Lohman and P. Seymour: Packing non-zero A-paths in group-labelled graphs, Combinatorica 26 (2006), 521\u2013532.","journal-title":"Combinatorica"},{"key":"4736_CR4","unstructured":"\u00c9. Colin de Verdi\u00e8re: Computational topology of graphs on surfaces, in: Handbook of Discrete and Computational Geometry, 3rd Ed. (C. D. Toth, J. O\u2019Rourke, and J. E. Goodman, eds., Chapman and Hall\/CRC, 2017), 605\u2013636 (Chap. 23), 2017."},{"key":"4736_CR5","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms, 3rd Ed., MIT Press, 2009."},{"key":"4736_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(85)90094-8","volume":"21","author":"U Derigs","year":"1985","unstructured":"U. Derigs: An efficient Dijkstra-like labeling method for computing shortest odd\/even paths, Information Processing Letters 21 (1985), 253\u2013258.","journal-title":"Information Processing Letters"},{"key":"4736_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E W Dijkstra","year":"1959","unstructured":"E. W. Dijkstra: A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959), 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"4736_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1090\/psapm\/070\/591","volume":"70","author":"J Erickson","year":"2012","unstructured":"J. Erickson: Combinatorial optimization of cycles and bases, Advances in Applied and Computational Topology 70 (2012), 195\u2013228.","journal-title":"Advances in Applied and Computational Topology"},{"key":"4736_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00454-003-2948-z","volume":"31","author":"J Erickson","year":"2004","unstructured":"J. Erickson and S. Har-Peled: Optimally cutting a surface into a disk, Discrete and Computational Geometry 31 (2004), 37\u201359.","journal-title":"Discrete and Computational Geometry"},{"key":"4736_CR10","doi-asserted-by":"crossref","unstructured":"K. Fox: Shortest non-trivial cycles in directed and undirected surface graphs, in: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), 352\u2013364, 2013.","DOI":"10.1137\/1.9781611973105.26"},{"key":"4736_CR11","unstructured":"T. Huynh: The Linkage Problem for Group-Labelled Graphs, Ph.D. Thesis, University of Waterloo, 2009."},{"key":"4736_CR12","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00493-017-3683-z","volume":"39","author":"T Huynh","year":"2019","unstructured":"T. Huynh, F. Joos and P. Wollan: A unified Erd\u0150s-P\u00f3sa theorem for constrained cycles, Combinatorica 39 (2019), 91\u2013133.","journal-title":"Combinatorica"},{"key":"4736_CR13","doi-asserted-by":"crossref","unstructured":"S. Iwata and Y. Kobayashi: A weighted linear matroid parity algorithm, SIAM Journal on Computing, 2021 (published online).","DOI":"10.1137\/17M1141709"},{"key":"4736_CR14","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/j.jctb.2005.08.001","volume":"96","author":"K Kawarabayashi","year":"2006","unstructured":"K. Kawarabayashi and P. Wollan: Non-zero disjoint cycles in highly connected group labelled graphs, Journal of Combinatorial Theory, Series B 96 (2006), 296\u2013301.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4736_CR15","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.jctb.2019.12.001","volume":"143","author":"Y Kawase","year":"2020","unstructured":"Y. Kawase, Y. Kobayashi and Y. Yamaguchi: Finding a path with two labels forbidden in group-labeled graphs, Journal of Combinatorial Theory, Series B 143 (2020), 65\u2013122.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4736_CR16","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1007\/s00453-016-0142-y","volume":"77","author":"Y Kobayashi","year":"2017","unstructured":"Y. Kobayashi and S. Toyooka: Finding a shortest non-zero path in group-labeled graphs via permanent computation, Algorithmica 77 (2017), 1128\u20131142.","journal-title":"Algorithmica"},{"key":"4736_CR17","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1002\/net.3230140403","volume":"14","author":"A S LaPaugh","year":"1984","unstructured":"A. S. LaPaugh and C. H. Papadimitriou: The even-path problem for graphs and digraphs, Networks 14 (1984), 507\u2013513.","journal-title":"Networks"},{"key":"4736_CR18","unstructured":"D. Lokshtanov, M. S. Ramanujan and S. Saurabh: The half-integral Erd\u0150s-P\u00f3sa property for non-null cycles, arXiv:1703.02866, 2017."},{"key":"4736_CR19","unstructured":"A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003."},{"key":"4736_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.dam.2016.06.001","volume":"214","author":"S Tanigawa","year":"2016","unstructured":"S. Tanigawa and Y. Yamaguchi: Packing non-zero A-paths via matroid matching, Discrete Applied Mathematics 214 (2016), 169\u2013178.","journal-title":"Discrete Applied Mathematics"},{"key":"4736_CR21","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C Thomassen","year":"1990","unstructured":"C. Thomassen: Embeddings of graphs with no short noncontractible cycles, Journal of Combinatorial Theory, Series B 48 (1990), 155\u2013177.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4736_CR22","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00493-011-2551-5","volume":"31","author":"P Wollan","year":"2011","unstructured":"P. Wollan: Packing cycles with modularity constraints, Combinatorica 31 (2011), 95\u2013126.","journal-title":"Combinatorica"},{"key":"4736_CR23","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1137\/130949877","volume":"30","author":"Y Yamaguchi","year":"2016","unstructured":"Y. Yamaguchi: Packing A-paths in group-labelled graphs via linear matroid parity, SIAM Journal on Discrete Mathematics 30 (2016), 474\u2013492.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4736_CR24","unstructured":"Y. Yamaguchi: Shortest disjoint $$\\cal{S}$$-paths via weighted linear matroid parity, in: Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), No. 63, 2016."},{"key":"4736_CR25","doi-asserted-by":"crossref","unstructured":"Y. Yamaguchi: A strongly polynomial algorithm for finding a shortest non-zero path in group-labeled graphs, in: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), 1923\u20131932, 2020.","DOI":"10.1137\/1.9781611975994.118"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4736-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-021-4736-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4736-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T10:08:44Z","timestamp":1701079724000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-021-4736-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,21]]},"references-count":25,"journal-issue":{"issue":"S2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["4736"],"URL":"https:\/\/doi.org\/10.1007\/s00493-021-4736-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,21]]},"assertion":[{"value":"8 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}