A subquadratic-time algorithm for decremental single-source shortest paths

We study dynamic (1 + ∊)-approximation algorithms for the single-source shortest paths problem in an unweighted undirected n-node m-edge graph under edge deletions. The fastest algorithm for this problem is an algorithm with O(n2+o(1)) total update time and constant query time by Bernstein and Rodit...

Full description

Saved in:
Bibliographic Details
Main Authors: Nanongkai, Danupon, Henzinger, Monika, Krinninger, Sebastian
Other Authors: School of Physical and Mathematical Sciences
Format: Conference or Workshop Item
Language:English
Published: 2015
Subjects:
Online Access:https://hdl.handle.net/10356/106740
http://hdl.handle.net/10220/25074
http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.79
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English