---
_id: '11876'
abstract:
- lang: eng
  text: "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.\r\n\r\nIn 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."
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger MH, Krinninger S, Nanongkai D. A subquadratic-time algorithm for
    decremental single-source shortest paths. In: <i>25th Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2014:1053-1072.
    doi:<a href="https://doi.org/10.1137/1.9781611973402.79">10.1137/1.9781611973402.79</a>'
  apa: 'Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2014). A subquadratic-time
    algorithm for decremental single-source shortest paths. In <i>25th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i> (pp. 1053–1072). Portland, OR, United States:
    Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611973402.79">https://doi.org/10.1137/1.9781611973402.79</a>'
  chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Subquadratic-Time
    Algorithm for Decremental Single-Source Shortest Paths.” In <i>25th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, 1053–72. Society for Industrial and Applied
    Mathematics, 2014. <a href="https://doi.org/10.1137/1.9781611973402.79">https://doi.org/10.1137/1.9781611973402.79</a>.
  ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A subquadratic-time algorithm
    for decremental single-source shortest paths,” in <i>25th Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, Portland, OR, United States, 2014, pp. 1053–1072.
  ista: 'Henzinger MH, Krinninger S, Nanongkai D. 2014. A subquadratic-time algorithm
    for decremental single-source shortest paths. 25th Annual ACM-SIAM Symposium on
    Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1053–1072.'
  mla: Henzinger, Monika H., et al. “A Subquadratic-Time Algorithm for Decremental
    Single-Source Shortest Paths.” <i>25th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Society for Industrial and Applied Mathematics, 2014, pp. 1053–72, doi:<a href="https://doi.org/10.1137/1.9781611973402.79">10.1137/1.9781611973402.79</a>.
  short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 25th Annual ACM-SIAM Symposium
    on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014,
    pp. 1053–1072.
conference:
  end_date: 2014-01-07
  location: Portland, OR, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2014-01-05
date_created: 2022-08-16T12:58:31Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-17T11:58:42Z
day: '01'
doi: 10.1137/1.9781611973402.79
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1137/1.9781611973402.79
month: '01'
oa: 1
oa_version: Published Version
page: 1053-1072
publication: 25th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - 978-1-61197-340-2
  isbn:
  - 978-1-61197-338-9
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: A subquadratic-time algorithm for decremental single-source shortest paths
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...