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 0(n(2) log n) space with a query time of 0(log n). No non-trivial solution was known for this problem.
Oracles for distances avoiding a link-failure / Demetrescu, Camil; M., Thorup. - (2002), pp. 838-843. (Intervento presentato al convegno 13th Annual ACM/SIAM Symposium on Discrete Algorithms tenutosi a SAN FRANCISCO, CA nel JAN 06-08, 2002).
Oracles for distances avoiding a link-failure
DEMETRESCU, Camil;
2002
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 0(n(2) log n) space with a query time of 0(log n). No non-trivial solution was known for this problem.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
