Technion, IEM faculty - Operations Research seminar
Speaker: Oren Weimann
Title: Fault-tolerant shortest paths
Date: 21/03/2011
Time: 12:30
Place: Bloomfield-527
Abstract:  <>
Or see below:
Abstract: In a network G whose edges occasionally fail, a shortest path P between two nodes s and t may have to
change accordingly. The "replacement paths" problem asks to compute, for every edge e in P, the shortest s-to-t path
that avoids e. This is a generalization of the fundamental shortest paths problem that is better suited for
real-world dynamic networks. In auction theory, the replacement paths problem is used to compute the Vickrey pricing
of edges owned by selfish agents. In my talk, I will present an O(Mn^{2.584}) time algorithm for the replacement
paths problem on general networks with edge-lengths in {-M,...,M}, and an O(n log^2n) time algorithm that works for
arbitrary edge-lengths provided that the underlying network is planar.
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>