{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T04:23:46Z","timestamp":1775622226756,"version":"3.50.1"},"reference-count":9,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS 1763817 and DMS-1800053"],"award-info":[{"award-number":["DMS 1763817 and DMS-1800053"]}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["A9550-19-1-0187"],"award-info":[{"award-number":["A9550-19-1-0187"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000183","name":"U. S. Army Research Office","doi-asserted-by":"publisher","award":["W911NF-16-1-0404"],"award-info":[{"award-number":["W911NF-16-1-0404"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every\n            <jats:italic>t<\/jats:italic>\n            , there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least\n            <jats:italic>t<\/jats:italic>\n            . In this article, we give an algorithm that finds a shortest odd hole, if one exists.\n          <\/jats:p>","DOI":"10.1145\/3447869","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:01:42Z","timestamp":1618876902000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Finding a Shortest Odd Hole"],"prefix":"10.1145","volume":"17","author":[{"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[{"name":"Princeton University, Edgbaston, Birmingham, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Seymour","sequence":"additional","affiliation":[{"name":"Princeton University, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,19]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"114","article-title":"F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind","volume":"10","author":"Berge Claude","year":"1961","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90098-M"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90357-L"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4301-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375720"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Combinatorial Analysis and Its Applications 19","author":"Gy\u00e1rf\u00e1s Andras","year":"1987"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.10.002"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447869","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447869","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:28Z","timestamp":1750268968000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,19]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3447869"],"URL":"https:\/\/doi.org\/10.1145\/3447869","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,19]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}