Given an undirected unweighted graph, the almost minimum cycle is defined as the cycle whose length is greater than that of a minimum cycle by at most one. Itai and Rodeh in a seminal paper in 1978 gave a simple O(n^2) algorithm to find such an almost minimum cycle. My question is, has it been improved ever since? If yes, which paper does that?

  • $\begingroup$ For the lazy, here's a Google-Scholar link to the paper. Here's a link to the papers that cite that one. As of August 2018, Google Scholar returns only four papers that cite that one and contain the phrase "Almost minimum". $\endgroup$ – Neal Young Aug 23 '18 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.