Abstract:
I will present some results from "Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems", by Virginia Vassilevska, Ryan Williams, and Raphael Yuster. This work appeared in the International Colloquium on Autotmata, Languages and Programming 2006. I will present their deterministic algorithm for finding the minimum weight cycle of length k. For a fixed (constant) k, the algorithm has running time that is sub-quadratic in m, the number of edges.