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: | , , |
---|---|
Other Authors: | |
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 |
id |
sg-ntu-dr.10356-106740 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1067402023-02-28T19:17:59Z A subquadratic-time algorithm for decremental single-source shortest paths Nanongkai, Danupon Henzinger, Monika Krinninger, Sebastian School of Physical and Mathematical Sciences Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (25th : 2014) DRNTU::Science::Mathematics::Discrete mathematics::Algorithms 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 Roditty (SODA 2011). In this paper, we improve the total update time to O(n1.8+o(1) + m1+o(1)) while keeping the query time constant. This running time is essentially tight when m = Ω(n1.8) since we need Ω(m) time even in the static setting. For smaller values of m, the running time of our algorithm is subquadratic, and is the first that breaks through the quadratic time barrier. In obtaining this result, we develop a fast algorithm for what we call center cover data structure. We also make non-trivial extensions to our previous techniques called lazy-update and monotone Even-Shiloach trees (ICALP 2013 and FOCS 2013). As by-products of our new techniques, we obtain two new results for the decremental all-pairs shortest-paths problem. Our first result is the first approximation algorithm whose total update time is faster than Õ(mn) for all values of m. Our second result is a new trade-off between the total update time and the additive approximation guarantee. Published version 2015-02-18T03:17:43Z 2019-12-06T22:17:21Z 2015-02-18T03:17:43Z 2019-12-06T22:17:21Z 2014 2014 Conference Paper Henzinger, M., Krinninger, S., & Nanongkai, D. (2014). A subquadratic-time algorithm for decremental single-source shortest paths. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1053-1072. https://hdl.handle.net/10356/106740 http://hdl.handle.net/10220/25074 http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.79 en © 2014 Society for Industrial and Applied Mathematics. This paper was published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following URL: [http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.79]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. 20 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Science::Mathematics::Discrete mathematics::Algorithms |
spellingShingle |
DRNTU::Science::Mathematics::Discrete mathematics::Algorithms Nanongkai, Danupon Henzinger, Monika Krinninger, Sebastian A subquadratic-time algorithm for decremental single-source shortest paths |
description |
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 Roditty (SODA 2011). In this paper, we improve the total update time to O(n1.8+o(1) + m1+o(1)) while keeping the query time constant. This running time is essentially tight when m = Ω(n1.8) since we need Ω(m) time even in the static setting. For smaller values of m, the running time of our algorithm is subquadratic, and is the first that breaks through the quadratic time barrier. In obtaining this result, we develop a fast algorithm for what we call center cover data structure. We also make non-trivial extensions to our previous techniques called lazy-update and monotone Even-Shiloach trees (ICALP 2013 and FOCS 2013). As by-products of our new techniques, we obtain two new results for the decremental all-pairs shortest-paths problem. Our first result is the first approximation algorithm whose total update time is faster than Õ(mn) for all values of m. Our second result is a new trade-off between the total update time and the additive approximation guarantee. |
author2 |
School of Physical and Mathematical Sciences |
author_facet |
School of Physical and Mathematical Sciences Nanongkai, Danupon Henzinger, Monika Krinninger, Sebastian |
format |
Conference or Workshop Item |
author |
Nanongkai, Danupon Henzinger, Monika Krinninger, Sebastian |
author_sort |
Nanongkai, Danupon |
title |
A subquadratic-time algorithm for decremental single-source shortest paths |
title_short |
A subquadratic-time algorithm for decremental single-source shortest paths |
title_full |
A subquadratic-time algorithm for decremental single-source shortest paths |
title_fullStr |
A subquadratic-time algorithm for decremental single-source shortest paths |
title_full_unstemmed |
A subquadratic-time algorithm for decremental single-source shortest paths |
title_sort |
subquadratic-time algorithm for decremental single-source shortest paths |
publishDate |
2015 |
url |
https://hdl.handle.net/10356/106740 http://hdl.handle.net/10220/25074 http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.79 |
_version_ |
1759857764539039744 |