Maintaining shortest paths under deletions in weighted directed graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

We present an improved algorithm for maintaining all-pairs (1 + ε) approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem was total update time O ̃(n 2√m/ε) for directed, unweighted graphs [2], and Õ(mn=ε) for undirected, unweighted graphs [12]. Both algorithms were randomized and had constant query time. Note that Õ(mn) is a natural bar- rier because even with a (1 + ε) approximation, there is no o(mn) combinatorial algorithm for the static all-pairs short- est path problem. Our algorithm works on directed, weighted graphs and has total (randomized) update time Õ(mnlog(R)=ε) where R is the ratio of the largest edge weight ever seen in the graph, to the smallest such weight (our query time is constant). Note that log(R) = O(log(n)) as long as weights are poly- nomial in n. Although Õ(mnlog(R)=ε) is the total time over all updates, our algorithm also requires a clearly unavoid- able constant time per update. Thus, we effectively expand the Õ (mn) total update time bound from undirected, un- weighted graphs to directed graphs with polynomial weights. This is in fact the first non-trivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (pre- vious algorithms could only handle small integer weights). By a well known reduction from decremental algorithms to fully dynamic ones [9], our improved decremental algorithm leads to improved query-update tradeoffs for fully dynamic (1 + ε) approximate APSP algorithm in directed graphs.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages725-734
Number of pages10
DOIs
StatePublished - 2013
Externally publishedYes
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
Country/TerritoryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation algorithms
  • Dynamic algorithms
  • Shortest paths

Fingerprint

Dive into the research topics of 'Maintaining shortest paths under deletions in weighted directed graphs'. Together they form a unique fingerprint.

Cite this