ALCOMFT-TR-01-175

Camil Demetrescu and Mikkel Thorup
Oracles for Distances Avoiding a Link-failure
Rome. Work packages 2 and 4. September 2001.

Abstract: For a directed graph G we consider queries of the form: `What is the shortest path distance from vertex x to vertex y in G avoiding a failed link (u,v), and what edge leaving x should we use to get on a such a shortest path?'' We show that an oracle for such queries can be stored in O(n²log n) space with a query time of O(log n). No non-trivial solution was known for this problem.

Postscript file: ALCOMFT-TR-01-175.ps.gz (142 kb).