On Dynamic Shortest Paths Problems

On Dynamic Shortest Paths Problems

0.00 Avg rating0 Votes
Article ID: iaor20118123
Volume: 61
Issue: 2
Start Page Number: 389
End Page Number: 401
Publication Date: Oct 2011
Journal: Algorithmica
Authors: ,
Abstract:

We obtain the following results related to dynamic versions of the shortest‐paths problem:

  • Reductions that show that the incremental and decremental single‐source shortest‐paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all‐pairs shortest‐paths problem. We also obtain slightly weaker results for the corresponding unweighted problems.
  • A randomized fully‐dynamic algorithm for the all‐pairs shortest‐paths problem in directed unweighted graphs with an amortized update time of ilde O ( m n ) (we use ilde O to hide small poly‐logarithmic factors) and a worst case query time is O(n 3/4).
  • A deterministic O(n 2log n) time algorithm for constructing an O(log n)‐spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single‐source shortest‐paths tree up to a given distance.
  • Reviews

    Required fields are marked *. Your email address will not be published.