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

----------------------------------------------------------