4
$\begingroup$

I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:

  • My primary focus is to achieve lowest possible query time ($O(1)$ would be perfect), it's the most important thing for me, this operation will be done very often (of course the price will be increased memory consumption, but I'm fine with that),
  • Graph is fully dynamic - both edges & vertices can be added/deleted - it would be nice if I didn't have to recompute everything from scratch,
  • $|V| = 10000$ (approximately).

I've search the Internet and skimmed through lots of articles, but didn't find anything that matched perfectly my case.

Any help and/or links would be highly appreciated.

$\endgroup$
4
$\begingroup$

theory results:

exact:

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

approximate:

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

implementation for road networks:

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato Fonseca F. Werneck: Customizable Route Planning. SEA 2011: 376-387

(updates only to cost of edges, might be possible to extend to addition and deletion of edges)

comment

none of the methods above achieves O(1) query time

note that if you use lots of space for a data structure, it probably means that you will need significant time to update the data structure in case the graph changes (low query time at the cost of high update time)

if updates are rare, it might be worth it. what is the application?

$\endgroup$
  • $\begingroup$ Depending on how the route planning algorithm's behavior and the OP's use case interact, he might be able to make it work by using a complete graph where edges that are not in the actual graph have a cost higher than the cost of the longest shortest path in the actual graph. $\;\;$ (The latter is always at most $\:\operatorname{diameter}(V) \cdot \text{highest_weight_edge_in_}V\:$.) $\;\;\;\;$ $\endgroup$ – user6973 Mar 18 '13 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.