Loading...
Please wait, while we are loading the content...
Similar Documents
Improved dynamic algorithms for maintaining approximate shortest paths under deletions
| Content Provider | CiteSeerX |
|---|---|
| Author | Bernstein, Aaron Roditty, Liam |
| Description | In 22nd ACM Symp. on Discrete Algorithms (SODA 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). • Given a source s, we present an algorithm that maintains (1 + ɛ)-approximate shortest paths from s with an expected total update time of Õ(n 2+O(1/ √ log n)) over all deletions (so the amortized time is about Õ(n2 /m)). The worstcase |
| File Format | |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Reasonable Query Time Approximate Shortest-path Problem Dynamic Algorithm Expected Total Update Time New Decremental Algorithm Update Time Barrier Not-too-sparse Graph Undirected Graph Amortized Time La Vega |
| Content Type | Text |
| Resource Type | Article |
