Journal article icon

Journal article

Finding a shortest odd hole

Abstract:
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.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/3447869

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
ORCID:
0000-0003-4489-5988
Publisher:
Association for Computing Machinery
Journal:
ACM Transactions on Algorithms More from this journal
Volume:
17
Issue:
2
Article number:
13
Publication date:
2021-04-19
Acceptance date:
2021-01-21
DOI:
EISSN:
1549-6333
ISSN:
1549-6325
Language:
English
Keywords:
Pubs id:
1136533
Local pid:
pubs:1136533
Deposit date:
2021-01-22

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP