{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:35:31Z","timestamp":1777520131066,"version":"3.51.4"},"reference-count":26,"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-4743-y","type":"journal-article","created":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T17:03:23Z","timestamp":1663779803000},"page":"1409-1438","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Packing Directed Cycles Quarter- and Half-Integrally"],"prefix":"10.1007","volume":"42","author":[{"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Muzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,21]]},"reference":[{"key":"4743_CR1","unstructured":"S. A. Amiri, K. Kawarabayashi, S. Kreutzer and P. Wollan: The Erd\u0150s-P\u00f3sa property for directed graphs, CoRR, arXiv:1603.025042016."},{"key":"4743_CR2","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00493-010-2455-9","volume":"30","author":"M Andrews","year":"2010","unstructured":"M. Andrews, J. Chuzhoy, V. Guruswami, S. Khanna, K. Talwar and L. Zhang: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Combinatorica 30 (2010), 485\u2013520.","journal-title":"Combinatorica"},{"key":"4743_CR3","unstructured":"T. Carpenter, A. Salmasi and A. Sidiropoulos: Routing symmetric demands in directed minor-free graphs with constant congestion, CoRR, abs\/1711.01692, 2017."},{"key":"4743_CR4","doi-asserted-by":"crossref","unstructured":"C. Chekuri and J. Chuzhoy: Large-treewidth graph decompositions and applications, In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pages 291\u2013300. ACM, 2013.","DOI":"10.1145\/2488608.2488645"},{"key":"4743_CR5","doi-asserted-by":"publisher","first-page":"40:1","DOI":"10.1145\/2820609","volume":"63","author":"C Chekuri","year":"2016","unstructured":"C. Chekuri and J. Chuzhoy: Polynomial bounds for the grid-minor theorem, Journal of the ACM, 63 (2016), 40:1\u201340:65.","journal-title":"Journal of the ACM"},{"key":"4743_CR6","doi-asserted-by":"crossref","unstructured":"C. Chekuri and A. Ene: The all-or-nothing flow problem in directed graphs with symmetric demand pairs, Mathematical Programming, 1\u201324, 2014.","DOI":"10.1007\/s10107-014-0856-z"},{"key":"4743_CR7","doi-asserted-by":"publisher","first-page":"2134","DOI":"10.1137\/17M1150694","volume":"32","author":"C Chekuri","year":"2018","unstructured":"C. Chekuri, A. Ene and M. Pilipczuk: Constant congestion routing of symmetric demands in planar directed graphs, SIAM Journal on Discrete Mathematics 32 (2018), 2134\u20132160.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4743_CR8","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna and F. Shepherd: Multicommodity flow, well-linked terminals, and routing problems, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), 183\u2013192. ACM, 2005.","DOI":"10.1145\/1060590.1060618"},{"key":"4743_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2893472","volume":"63","author":"J Chuzhoy","year":"2016","unstructured":"J. Chuzhoy and S. Li: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2, Journal of the ACM 63 (2016), 1\u201351.","journal-title":"Journal of the ACM"},{"key":"4743_CR10","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.jctb.2020.09.010","volume":"146","author":"J Chuzhoy","year":"2021","unstructured":"J. Chuzhoy and Z. Tan: Towards tight(er) bounds for the excluded grid theorem, Journal of Combinatorial Theory, Series B 146 (2021), 219\u2013265.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4743_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00493-008-2140-4","volume":"28","author":"E D Demaine","year":"2008","unstructured":"E. D. Demaine and M. Hajiaghayi: Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica 28 (2008), 19\u201336.","journal-title":"Combinatorica"},{"key":"4743_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P Erd\u0150s","year":"1965","unstructured":"P. Erd\u0150s and L. P\u00f3sa: On independent circuits contained in a graph, Canadian Journal of Mathematics 17 (1965), 347\u2013352.","journal-title":"Canadian Journal of Mathematics"},{"key":"4743_CR13","doi-asserted-by":"crossref","unstructured":"M. Hatzel, K. Kawarabayashi and S. Kreutzer: Polynomial planar directed grid theorem, in: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), 1465\u20131484, 2019.","DOI":"10.1137\/1.9781611975482.89"},{"key":"4743_CR14","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"T. Johnson, N. Robertson, P. D. Seymour and R. Thomas: Directed tree-width, Journal of Combinatorial Theory, Series B 82 (2001), 138\u2013154.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4743_CR15","unstructured":"T. Johnson, N. Robertson, P. D. Seymour and R. Thomas: Excluding a grid minor in planar digraphs, CoRR, arXiv:1510.00473, 2001."},{"key":"4743_CR16","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and S. Kreutzer: The directed grid theorem, CoRR, arXiv:1411.5681v1, 2014.","DOI":"10.1145\/2746539.2746586"},{"key":"4743_CR17","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and S. Kreutzer: The directed grid theorem, in: Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC 2015), 655\u2013664, 2015.","DOI":"10.1145\/2746539.2746586"},{"key":"4743_CR18","unstructured":"S. Kreutzer and S. Ordyniak: Width-measures for directed graphs and algorithmic applications, in: Quantitative Graph Theory: Mathematical Foundations and Applications, Springer, 2014."},{"key":"4743_CR19","series-title":"LIPIcs","first-page":"1","volume-title":"27th Annual European Symposium on Algorithms (ESA 2019)","author":"T Masa\u0159\u00edk","year":"2019","unstructured":"T. Masa\u0159\u00edk, I. Muzi, M. Pilipczuk, P. Rz\u0105\u017cewski and M. Sorge: Packing Directed Circuits Quarter-Integrally, in: 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of LIPIcs, pages 1\u201313, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"4743_CR20","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S1571-0653(05)80061-7","volume":"3","author":"B Reed","year":"1999","unstructured":"B. Reed: Introducing directed tree width, Electronic Notes in Discrete Mathematics 3 (1999), 222\u2013229.","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"4743_CR21","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01271272","volume":"16","author":"B Reed","year":"1996","unstructured":"B. Reed, N. Robertson, P. Seymour and R. Thomas: Packing directed circuits, Combinatorica 16 (1996), 535\u2013554.","journal-title":"Combinatorica"},{"key":"4743_CR22","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.ejc.2011.09.004","volume":"33","author":"B A Reed","year":"2012","unstructured":"B. A. Reed and D. R. Wood: Polynomial treewidth forces a large grid-like-minor, Eur. J. Comb. 33 (2012), 374\u2013379.","journal-title":"Eur. J. Comb."},{"key":"4743_CR23","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"N. Robertson and P. D. Seymour: Graph minors. III. Planar tree-width, J. Comb. Theory, Ser. B 36 (1984), 49\u201364.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"4743_CR24","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"N. Robertson and P. D. Seymour: Graph minors. V. Excluding a planar graph, J. Comb. Theory, Ser. B 41 (1986), 92\u2013114.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"4743_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N Robertson","year":"1994","unstructured":"N. Robertson, P. D. Seymour and R. Thomas: Quickly excluding a planar graph, J. Comb. Theory, Ser. B 62 (1994), 323\u2013348.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"4743_CR26","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P D Seymour","year":"1995","unstructured":"P. D. Seymour: Packing directed circuits fractionally, Combinatorica 15 (1995), 281\u2013288.","journal-title":"Combinatorica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4743-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-021-4743-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4743-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T16:34:12Z","timestamp":1675355652000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-021-4743-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,21]]},"references-count":26,"journal-issue":{"issue":"S2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["4743"],"URL":"https:\/\/doi.org\/10.1007\/s00493-021-4743-y","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":"9 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 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"}}]}}