Finding a shortest odd hole
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 t, there is a polynomial-time algor...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2021
|
| _version_ | 1797104937932423168 |
|---|---|
| author | Chudnovsky, M Scott, A Seymour, P |
| author_facet | Chudnovsky, M Scott, A Seymour, P |
| author_sort | Chudnovsky, M |
| collection | OXFORD |
| description | 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 t, there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t. In this article, we give an algorithm that finds a shortest odd hole, if one exists. |
| first_indexed | 2024-03-07T06:40:27Z |
| format | Journal article |
| id | oxford-uuid:f919abe2-a066-4ca5-bfcd-5eee1dfd5efa |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:40:27Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:f919abe2-a066-4ca5-bfcd-5eee1dfd5efa2022-03-27T12:55:25ZFinding a shortest odd holeJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f919abe2-a066-4ca5-bfcd-5eee1dfd5efaEnglishSymplectic ElementsAssociation for Computing Machinery2021Chudnovsky, MScott, ASeymour, PAn 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 t, there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t. In this article, we give an algorithm that finds a shortest odd hole, if one exists. |
| spellingShingle | Chudnovsky, M Scott, A Seymour, P Finding a shortest odd hole |
| title | Finding a shortest odd hole |
| title_full | Finding a shortest odd hole |
| title_fullStr | Finding a shortest odd hole |
| title_full_unstemmed | Finding a shortest odd hole |
| title_short | Finding a shortest odd hole |
| title_sort | finding a shortest odd hole |
| work_keys_str_mv | AT chudnovskym findingashortestoddhole AT scotta findingashortestoddhole AT seymourp findingashortestoddhole |