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...
Saved in:
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 |
Similar Items
-
Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem
by: Liu, Shuqing
Published: (2021) -
Combinatorial algorithms for scheduling jobs to minimize server usage time
by: Ren, Runtian
Published: (2018) -
Standardized signature algorithms on ultra-constrained 4-bit MCU
by: Chen, Chien-Ning, et al.
Published: (2013) -
AGV scheduling algorithms for container ports
by: Lim, Hyun Jeong
Published: (2019) -
Game theory based algorithms for community detection
by: Radhika Arava
Published: (2015)