演讲人： Uri Zwick 特拉维夫大学
时间： 2011-10-20 14:00-2011-10-20 15:00
地点：FIT 1-222
课件下载：点击下载
内容：

We present an All-Pairs Shortest Paths (APSP) algorithm whose expected running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0, 1] is O(n^2). This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the expected number of locally shortest paths in such randomly weighted graphs is O(n^2). We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log^2 n) expected time.

 

Joint work with Yuval Peres, Benny Sudakov and Uri Zwick

个人简介:

Uri Zwick received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University. He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.