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