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: <http://ie.technion.ac.il/seminar_files/1299578276_Oren_Weimann_seminar.doc> 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 <techm@math.technion.ac.il> Announcement from: <levinas@techunix.technion.ac.il>