Technion Computer Science Colloquium 03/05/2011 Time+Place : Tuesday 03/05/2011 14:30 room 337-8 Taub Bld. Speaker : Liam Roditty Affiliation: Computer Science Department, Bar-Ilan University Host : Johann Makowsky Title : The Minimum Weight Cycle Problem Abstract : We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a graph of nonnegative edge weights. Extending the seminal work of Itai and Rodeh [SIAM J. Computing 1978 and STOC'77] on minimum cycle in unweighted graphs, we show that the minimum weight cycle problem in a (directed or undirected) $n$-node graph with weights in $\{1,\ldots, M\}$ can be efficiently reduced to finding a minimum weight {\em triangle} in an $\Theta(n)-$node graph with weights in $\{1,\ldots,O(M)\}$. We also show that given a weighted undirected graph $G(V,E,w)$, with a minimum cycle of weight $t^*$ whose maximal edge weight is $w^*$ it is possible to efficiently compute the following approximations: 1. For integral weights from the range $[1,M]$ we report a cycle of weight at most $\frac{4}{3}t^*$ in $O(n^2\log n(\log n + \log M))$ time. 2. For integral weights from the range $[1,M]$ we report a cycle of weight at most $t^* + w^*$ in $O(n^2\log n(\log n + \log M))$ time. 3. For non-negative real edge weights and for any $\eps>0$ we report a cycle of weight at most $(\frac{4}{3}+\eps)t^*$ in $O(\frac{1}{\eps}n^2\log n(\log \log n))$ time. The talk is based on joint works with Roei Tov and with Virginia Vassilevska Williams. Short Bio: Liam Roditty received the B.A. degree (with distinction) in 1998 from Tel-Aviv University, Israel, the M.Sc. degree (with distinction) in 2001 from Tel-Aviv University, Israel, and the Ph.D. degree in 2006 from Tel-Aviv University, Israel, all in computer science. He then spent two years at the Weizmann Institute of Science as a post-doctoral fellow. In 2008 he joined the Department of Computer Science at Bar-Ilan University as a Senior Lecturer. His research interests include algorithmic questions in graph theory, dynamic algorithms, routing and fault-tolerance. Refreshments served from 14:15 on, Lecture starts at 14:30 ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>