TY - GEN
T1 - Improved distance oracles for avoiding link-failure
AU - Chowdhury, Rezaul Alam
AU - Ramachandran, Vijaya
PY - 2002
Y1 - 2002
N2 - We consider the problem of preprocessing an edge-weighted directed graph to answer queries that ask for the shortest path from any given vertex to another avoiding a failed link. We present two algorithms that improve on earlier results for this problem. Our first algorithm, which is a modification of an earlier method, improves the query time to a constant while maintaining the earlier bounds for preprocessing time and space. Our secondresult is a new algorithm whose preprocessing time is considerably faster than earlier results and whose query time and space are worse by no more than a logarithmic factor.
AB - We consider the problem of preprocessing an edge-weighted directed graph to answer queries that ask for the shortest path from any given vertex to another avoiding a failed link. We present two algorithms that improve on earlier results for this problem. Our first algorithm, which is a modification of an earlier method, improves the query time to a constant while maintaining the earlier bounds for preprocessing time and space. Our secondresult is a new algorithm whose preprocessing time is considerably faster than earlier results and whose query time and space are worse by no more than a logarithmic factor.
UR - https://www.scopus.com/pages/publications/84878641997
U2 - 10.1007/3-540-36136-7_46
DO - 10.1007/3-540-36136-7_46
M3 - Conference contribution
SN - 3540001425
SN - 9783540001423
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 523
EP - 534
BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Y2 - 21 November 2002 through 23 November 2002
ER -