{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:15Z","timestamp":1750307415787,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":79,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806785","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"695-704","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Odd cycle packing"],"prefix":"10.1145","author":[{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce","family":"Reed","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1016\/0166-218X(89)90031-0"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1017\/S0963548302005461"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1137\/S0097539793251219"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1016\/j.jctb.2008.07.006"},{"key":"e_1_3_2_1_5_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA'03)","author":"Khanna S.","year":"2003","unstructured":". Chekuri and S. Khanna , Edge disjoint paths revisited , ACM-SIAM Symposium on Discrete Algorithms (SODA'03) , 628--637, ( 2003 ). . Chekuri and S. Khanna,Edge disjoint paths revisited, ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 628--637, (2003)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1007\/s00493-006-0030-1"},{"key":"e_1_3_2_1_7_1","volume-title":"Puerto Rico","author":"V.","year":"1985","unstructured":". Dejter and V. Neumann-lara , Unboundedness for generalized odd cycle traversability anda Gallai conjecture, paper presented at the Fourth Caribbean Conference on Computing , Puerto Rico , 1985 . . Dejter and V. Neumann-lara,Unboundedness for generalized odd cycle traversability anda Gallai conjecture, paper presented at the Fourth Caribbean Conference on Computing, Puerto Rico, 1985."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1109\/SFCS.2005.14"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1006\/jctb.1998.1862"},{"unstructured":"R. Diestel K. Kawarabayashi T. M\u00fcller and P. Wollan On the structure theorem of the excluded minor theorem of large tree-width submitted. R. Diestel K. Kawarabayashi T. M\u00fcller and P. Wollan On the structure theorem of the excluded minor theorem of large tree-width submitted.","key":"e_1_3_2_1_10_1"},{"key":"e_1_3_2_1_11_1","first-page":"3","volume":"9","author":"P\u00f3sa L.","year":"1962","unstructured":". Erd\u00f6s and L. P\u00f3sa ,On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen , 9 ( 1962 ), 3 -- 12 . . Erd\u00f6s and L. P\u00f3sa,On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen, 9 (1962), 3--12.","journal-title":"Math. Debrecen"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1016\/0304-3975(80)90009-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.5555\/1230720.1230731"},{"key":"e_1_3_2_1_14_1","first-page":"49","volume":"1990","author":"Korte B.","unstructured":". Frank,Packing paths, cuts and circuits -- a survey, in Paths, Flows and VLSI-Layout B. Korte , L. Lov\u00e1sz , H.J. Promel and A. Schrijver . Eds.Berlin: Springer-Verlag 1990 , 49 -- 100 . . Frank,Packing paths, cuts and circuits -- a survey, in Paths, Flows and VLSI-Layout B. Korte, L. Lov\u00e1sz, H.J. Promel and A. Schrijver. Eds.Berlin: Springer-Verlag 1990, 49--100.","journal-title":"Springer-Verlag"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1016\/j.jctb.2008.03.006"},{"key":"e_1_3_2_1_16_1","volume-title":"Combinatorica, 18","author":"Goemans X.","year":"1998","unstructured":". X. Goemans and D.P. Williamson , Primal-dual approximation algorithms for feedback problems in planar graphs , Combinatorica, 18 ( 1998 ), 37--59. . X. Goemans and D.P. Williamson, Primal-dual approximation algorithms for feedback problems in planar graphs, Combinatorica, 18 (1998), 37--59."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/301250.301262"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1137\/0204019"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1007\/BF01917434"},{"unstructured":". Hunyh The linkage problem for group-labelled graphs Ph. D Thesis University of Waterloo 2009. . Hunyh The linkage problem for group-labelled graphs Ph. D Thesis University of Waterloo 2009.","key":"e_1_3_2_1_20_1"},{"doi-asserted-by":"crossref","unstructured":". Ibaraki and H. Nagamochi A linear time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph Algorithmica 7(1992) 583--596. . Ibaraki and H. Nagamochi A linear time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph Algorithmica 7(1992) 583--596.","key":"e_1_3_2_1_21_1","DOI":"10.1007\/BF01758778"},{"unstructured":". Kapadia Z. Li and B. Reed A linear time algorithm to test the 2-paths problem submitted. . Kapadia Z. Li and B. Reed A linear time algorithm to test the 2-paths problem submitted.","key":"e_1_3_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1016\/j.jctb.2006.04.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1016\/j.disc.2004.07.007"},{"volume-title":"IPCO'08","unstructured":". Kawarabayashi,Improved alogirthm for find a cycle through elements , IPCO'08 , 374--384. . Kawarabayashi,Improved alogirthm for find a cycle through elements, IPCO'08, 374--384.","key":"e_1_3_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1016\/j.jctb.2008.12.001"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1016\/j.jctb.2005.08.001"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1007\/s00493-007-2213-9"},{"key":"e_1_3_2_1_29_1","volume-title":"Discrete Math., 307","author":"Nakamoto A.","year":"2007","unstructured":". Kawarabayashi and A. Nakamoto , The Erdos-P\u00f3sa property for odd cycles on an orientable fixed surface , Discrete Math., 307 ( 2007 ), 764--768. . Kawarabayashi and A. Nakamoto,The Erdos-P\u00f3sa property for odd cycles on an orientable fixed surface, Discrete Math., 307 (2007), 764--768."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1145\/1250790.1250848"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1145\/1374376.1374443"},{"key":"e_1_3_2_1_32_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Reed B.","year":"2008","unstructured":". Kawarabayashi and B. Reed , A nearly linear time algorithm for the half disjoint paths packing , ACM-SIAM Symposium on Discrete Algorithms (SODA'08) , 446--454, ( 2008 ). . Kawarabayashi and B. Reed,A nearly linear time algorithm for the half disjoint paths packing, ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 446--454, (2008)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.5555\/1496770.1496898"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1007\/s00493-009-2178-y"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1109\/FOCS.2008.53"},{"unstructured":". Kawarabayashi Y. Kobayashi and B. Reed The disjoint paths problem in quaratic time submitted. . Kawarabayashi Y. Kobayashi and B. Reed The disjoint paths problem in quaratic time submitted.","key":"e_1_3_2_1_36_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.5555\/1873601.1873632"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1002\/net.1975.5.1.45"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1007\/BF02579141"},{"key":"e_1_3_2_1_40_1","first-page":"37","volume":"38","year":"1982","unstructured":". Kostochka,The minimum Hadwiger number for graphs with a given mean degree of vertices(in Russian) , Metody Diskret. Analiz. 38 ( 1982 ), 37 -- 58 . . Kostochka,The minimum Hadwiger number for graphs with a given mean degree of vertices(in Russian), Metody Diskret. Analiz. 38 (1982), 37--58.","journal-title":"Metody Diskret. Analiz."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1145\/1290672.1290685"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.4153\/CJM-1992-075-0"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen , Graphs on Surfaces , Johns Hopkins University Press , Baltimore, MD , 2001 . B. Mohar and C. Thomassen,Graphs on Surfaces,Johns Hopkins University Press, Baltimore, MD, 2001."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1142\/S0129054100000247"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_45_1","DOI":"10.1145\/129712.129734"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1016\/0166-218X(94)00104-L"},{"key":"e_1_3_2_1_47_1","first-page":"87","volume-title":"a new connectivity measure and some applications,in \"Surveys in Combinatorics","year":"1997","unstructured":". Reed,Tree width and tangles : a new connectivity measure and some applications,in \"Surveys in Combinatorics , 1997 (London)\",London Math. Soc. Lecture Note Ser. 241,Cambridge Univ. Press , Cambridge, 1997, pp. 87 -- 162 . . Reed,Tree width and tangles: a new connectivity measure and some applications,in \"Surveys in Combinatorics, 1997 (London)\",London Math. Soc. Lecture Note Ser. 241,Cambridge Univ. Press, Cambridge, 1997, pp. 87--162."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.1007\/s004930050056"},{"unstructured":". Reed Rooted Routing via Graph Minors to appear. . Reed Rooted Routing via Graph Minors to appear.","key":"e_1_3_2_1_49_1"},{"key":"e_1_3_2_1_50_1","volume-title":"WA, 1991), 295--301","author":"Reed B.","year":"1993","unstructured":"B. Reed , N. Robertson , A. Schrijver and P. D. Seymour , Finding disjoint trees in planar graphs in linear time. Graph structure theory (Seattle , WA, 1991), 295--301 , Contemp. Math., 147, Amer. Math. Soc., Providenc, RI , 1993 . B. Reed, N. Robertson, A. Schrijver and P. D. Seymour,Finding disjoint trees in planar graphs in linear time. Graph structure theory (Seattle, WA, 1991), 295--301, Contemp. Math., 147, Amer. Math. Soc., Providenc, RI, 1993."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1016\/j.orl.2003.10.009"},{"unstructured":"B. Reed and D. Wood A linear time algorithm to find a separator in a graph with anexcluded minor submitted. B. Reed and D. Wood A linear time algorithm to find a separator in a graph with anexcluded minor submitted.","key":"e_1_3_2_1_52_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.5555\/645907.673277"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_54_1","DOI":"10.1016\/0095-8956(84)90013-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_55_1","DOI":"10.1016\/0095-8956(86)90030-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_56_1","DOI":"10.1016\/0095-8956(88)90070-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_57_1","DOI":"10.1016\/0095-8956(90)90063-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_58_1","DOI":"10.1016\/0095-8956(91)90061-N"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_59_1","DOI":"10.1006\/jctb.1994.1007"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_60_1","DOI":"10.1006\/jctb.1995.1034"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_61_1","DOI":"10.1006\/jctb.1995.1006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_62_1","DOI":"10.1016\/S0095-8956(03)00042-X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_63_1","DOI":"10.1006\/jctb.1999.1919"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_64_1","DOI":"10.1016\/j.jctb.2008.08.003"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_65_1","DOI":"10.1016\/j.jctb.2007.12.007"},{"key":"e_1_3_2_1_66_1","first-page":"267","volume-title":"An outline of a disjoint paths algorithm,in: \"Paths, Flows, and VLSI-Layout,\"B","author":"Seymour P. D.","year":"1990","unstructured":". Robertson and P. D. Seymour , An outline of a disjoint paths algorithm,in: \"Paths, Flows, and VLSI-Layout,\"B . Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver (Eds.),Springer-Verlag, Berlin , 1990 , pp. 267 -- 292 . . Robertson and P. D. Seymour,An outline of a disjoint paths algorithm,in: \"Paths, Flows, and VLSI-Layout,\"B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver (Eds.),Springer-Verlag, Berlin, 1990, pp. 267--292."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_67_1","DOI":"10.1006\/jctb.1994.1073"},{"volume-title":"Schrijver,Combinatorial Optimization: Polyhedra and Efficiency, number 24 inAlgorithm and Combinatorics","year":"2003","unstructured":". Schrijver,Combinatorial Optimization: Polyhedra and Efficiency, number 24 inAlgorithm and Combinatorics , Springer Verlag , 2003 . . Schrijver,Combinatorial Optimization: Polyhedra and Efficiency, number 24 inAlgorithm and Combinatorics, Springer Verlag, 2003.","key":"e_1_3_2_1_68_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_69_1","DOI":"10.1016\/0095-8956(80)90075-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_70_1","DOI":"10.1016\/0012-365X(80)90158-2"},{"key":"e_1_3_2_1_71_1","first-page":"431","volume":"419","author":"Graham R. L.","year":"1985","unstructured":". Seymour, Matroid minors, Handbook of Combinatorics,(Eds.: R. L. Graham , M. Gr\u00f6tschel and L. L\u00f3vasz). North-Holland , Amsterdam , 1985 , 419 -- 431 . . Seymour, Matroid minors, Handbook of Combinatorics,(Eds.: R. L. Graham, M. Gr\u00f6tschel and L. L\u00f3vasz). North-Holland,Amsterdam, 1985, 419--431.","journal-title":"Amsterdam"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_72_1","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_3_2_1_73_1","volume-title":"SIAM","author":"Tarjan E.","year":"1983","unstructured":". E. Tarjan ,Data Structures and network algorithms , SIAM , Philadelphia, PA , 1983 . .E. Tarjan,Data Structures and network algorithms, SIAM, Philadelphia, PA, 1983."},{"volume-title":"Theory of computing systems, 39","year":"2004","unstructured":". Tholey,Solving the 2-disjoint paths problem in nearly linear time , Theory of computing systems, 39 ( 2004 ), 51--78. . Tholey,Solving the 2-disjoint paths problem in nearly linear time, Theory of computing systems, 39 (2004), 51--78.","key":"e_1_3_2_1_74_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_75_1","DOI":"10.1017\/S0305004100061521"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_76_1","DOI":"10.1006\/jctb.2000.2013"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_77_1","DOI":"10.1016\/S0195-6698(80)80039-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_78_1","DOI":"10.1002\/jgt.3190120111"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_79_1","DOI":"10.1007\/BF01594196"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC'10","name":"STOC'10: Symposium on Theory of Computing","location":"Cambridge Massachusetts USA"},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":79,"alternative-id":["10.1145\/1806689.1806785","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806785","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}