ICS Theory Group

CompSci 269S, Winter 2008: Theory Seminar

Mar 7, 2008, 1:00pm in Bren Hall 1423

Fast Algorithms for Minimum Weight Constant Length Cycles in Edge-Weighted Graphs

presented by Mike Nelson

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.