{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:35:13Z","timestamp":1777520113513,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,12,15]],"date-time":"2006-12-15T00:00:00Z","timestamp":1166140800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2007,3,12]]},"DOI":"10.1007\/s10107-006-0063-7","type":"journal-article","created":{"date-parts":[[2006,12,14]],"date-time":"2006-12-14T13:08:45Z","timestamp":1166101725000},"page":"71-91","source":"Crossref","is-referenced-by-count":15,"title":["Approximate min\u2013max relations for odd cycles in planar graphs"],"prefix":"10.1007","volume":"110","author":[{"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Hardy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce","family":"Reed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Vetta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,12,15]]},"reference":[{"key":"63_CR1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0012-365X(76)90147-3","volume":"16","author":"K. Appel","year":"1976","unstructured":"Appel K. and Haken W. (1976). A proof of the four color theorem. Discrete Math. 16: 179\u2013180","journal-title":"Discrete Math."},{"key":"63_CR2","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0020-0190(02)00274-0","volume":"84","author":"A. Caprara","year":"2002","unstructured":"Caprara A. and Rizzi R. (2002). Packing triangles in bounded degree graphs. Inform. Process Lett. 84: 175\u2013180","journal-title":"Inform. Process Lett."},{"key":"63_CR3","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth R.P. (1950). A decomposition theorem for partially ordered sets. Ann. Math. 51: 161\u2013166","journal-title":"Ann. Math."},{"key":"63_CR4","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P. Erd\u00f6s","year":"1965","unstructured":"Erd\u00f6s P. and P\u00f3sa L. (1965). On independent circuits contained in a graph. Canad. J. Math. 17: 347\u2013352","journal-title":"Canad. J. Math."},{"key":"63_CR5","unstructured":"Fiorini, S., Hardy, N., Reed, B., Vetta, A.: Planar graph bipartization in linear time. Discr. Appl. Math. (in press)"},{"key":"63_CR6","unstructured":"Frank, A.: A survey on T-joins, T-cuts, and conservative weightings. In: Combinatorics, Paul Erd\u00f6s is eighty, vol. 2, pp. 213\u2013252. Keszthely, 1993, J\u00e1nos Bolyai Mathematical Society, Budapest (1996)"},{"key":"63_CR7","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey M.R. and Johnson D.S. (1977). The rectilinear Steiner tree problem is NP-complete. SIAM. J. Appl. Math. 32: 826\u2013834","journal-title":"SIAM. J. Appl. Math."},{"key":"63_CR8","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/PL00009810","volume":"18","author":"M.X. Goemans","year":"1998","unstructured":"Goemans M.X. and Williamson D.P. (1998). Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica 18: 37\u201359","journal-title":"Combinatorica"},{"key":"63_CR9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"Hadlock F. (1975). Finding a maximum cut of a planar graph in polynomial time. SIAM. J. Comput. 4: 221\u2013225","journal-title":"SIAM. J. Comput."},{"key":"63_CR10","unstructured":"Hardy, N.: Odd cycles in planar graphs. Master\u2019s Thesis, McGill University, Montreal, Canada (June 2005)"},{"key":"63_CR11","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0095-8956(03)00078-9","volume":"90","author":"D. Kr\u00e1l","year":"2004","unstructured":"Kr\u00e1l D. and Voss H. (2004). Edge-disjoint odd cycles in planar graphs. J. Combin. Theory. Ser. B 90: 107\u2013120","journal-title":"J. Combin. Theory. Ser. B"},{"key":"63_CR12","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF01902352","volume":"26","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L. (1975). 2-matchings and 2-covers of hypergraphs. Acta. Math. Acad. Sci. Hungar. 26: 433\u2013444","journal-title":"Acta. Math. Acad. Sci. Hungar."},{"key":"63_CR13","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s004930100024","volume":"21","author":"D. Rautenbach","year":"2001","unstructured":"Rautenbach D. and Reed B. (2001). The Erd\u0151s-P\u00f3sa property for odd cycles in highly connected graphs. Combinatorica 21: 267\u2013278","journal-title":"Combinatorica"},{"key":"63_CR14","doi-asserted-by":"crossref","unstructured":"Reed, B.: Mangoes and blueberries. Combinatorica 19, 267\u2013296 (1999)","DOI":"10.1007\/s004930050056"},{"key":"63_CR15","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed B., Smith K. and Vetta A. (2004). Finding odd cycle transversals. Oper. Res. Lett. 32: 299\u2013301","journal-title":"Oper. Res. Lett."},{"key":"63_CR16","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"Robertson N., Sanders D., Seymour P. and Thomas R. (1997). The four colour theorem. J. Combin. Theory. Ser. B 70: 2\u201344","journal-title":"J. Combin. Theory. Ser. B"},{"key":"63_CR17","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and efficiency, vol. C. Springer, Berlin Heidelberg New York (2003)"},{"issue":"3","key":"63_CR18","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1112\/plms\/s3-42.1.178","volume":"42","author":"P. Seymour","year":"1981","unstructured":"Seymour P. (1981). On odd cuts and plane multicommodity flows. Proc. London Math Soc 42(3): 178\u2013192","journal-title":"Proc. London Math Soc"},{"key":"63_CR19","volume-title":"Approximation algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani V.V. (2001). Approximation algorithms. Springer, Berlin Heidelberg New York"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0063-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0063-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0063-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:01Z","timestamp":1559123401000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0063-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12,15]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3,12]]}},"alternative-id":["63"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0063-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12,15]]}}}