Minimum Weight Cycles and Triangles: Equivalences and Algorithms

Liam Roditty, Virginia Vassilevska Williams

We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirec…