TY - GEN
T1 - Improved dynamic algorithms for maintaining approximate shortest paths under deletions
AU - Bernstein, Aaron
AU - Roditty, Liam
PY - 2011
Y1 - 2011
N2 - We present the first dynamic shortest paths algorithms that make any progress beyond a longstanding O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas).
AB - We present the first dynamic shortest paths algorithms that make any progress beyond a longstanding O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas).
UR - http://www.scopus.com/inward/record.url?scp=79955714504&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79955714504&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973082.104
DO - 10.1137/1.9781611973082.104
M3 - Conference contribution
AN - SCOPUS:79955714504
SN - 9780898719932
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1355
EP - 1365
BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
PB - Association for Computing Machinery
ER -