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.
2002
9780898715132
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/50560
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 19
social impact