Finding a Shortest Odd Hole

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Article number3447869
JournalACM Transactions on Algorithms
Volume17
Issue number2
DOIs
StatePublished - Jun 2021

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Induced subgraph
  • recognition algorithm
  • shortest odd hole

Fingerprint

Dive into the research topics of 'Finding a Shortest Odd Hole'. Together they form a unique fingerprint.

Cite this