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

• 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: DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
• 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
• Institution: Nanyang Technological University

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...