---
_id: '11870'
abstract:
- lang: eng
  text: "We consider dynamic algorithms for maintaining Single-Source Reachability
    (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed
    graphs under edge deletions (decremental algorithms). The previous fastest algorithm
    for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it
    has O(1) query time and O(mn) total update time (i.e., linear amortized update
    time if all edges are deleted). This algorithm serves as a building block for
    several other dynamic algorithms. The question whether its total update time can
    be improved is a major, long standing, open problem.\r\n\r\nIn this paper, we
    answer this question affirmatively. We obtain a randomized algorithm which, in
    a simplified form, achieves an Õ(mn0.984) expected total update time for SSR and
    (1 + ε)-approximate SSSP, where Õ(·) hides poly log n. We also extend our algorithm
    to achieve roughly the same running time for Strongly Connected Components (SCC),
    improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that
    improves the Õ (mn log W)-time algorithm of Bernstein (STOC 2013) for approximating
    SSSP on weighted directed graphs, where the edge weights are integers from 1 to
    W. All our algorithms have constant query time in the worst case."
article_number: 674 - 683
article_processing_charge: No
arxiv: 1
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 M, Krinninger S, Nanongkai D. Sublinear-time decremental algorithms
    for single-source reachability and shortest paths on directed graphs. In: <i>46th
    Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery;
    2014. doi:<a href="https://doi.org/10.1145/2591796.2591869">10.1145/2591796.2591869</a>'
  apa: 'Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2014). Sublinear-time
    decremental algorithms for single-source reachability and shortest paths on directed
    graphs. In <i>46th Annual ACM Symposium on Theory of Computing</i>. New York,
    NY, United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/2591796.2591869">https://doi.org/10.1145/2591796.2591869</a>'
  chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
    Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed
    Graphs.” In <i>46th Annual ACM Symposium on Theory of Computing</i>. Association
    for Computing Machinery, 2014. <a href="https://doi.org/10.1145/2591796.2591869">https://doi.org/10.1145/2591796.2591869</a>.
  ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time decremental
    algorithms for single-source reachability and shortest paths on directed graphs,”
    in <i>46th Annual ACM Symposium on Theory of Computing</i>, New York, NY, United
    States, 2014.
  ista: 'Henzinger M, Krinninger S, Nanongkai D. 2014. Sublinear-time decremental
    algorithms for single-source reachability and shortest paths on directed graphs.
    46th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of
    Computing, 674–683.'
  mla: Henzinger, Monika, et al. “Sublinear-Time Decremental Algorithms for Single-Source
    Reachability and Shortest Paths on Directed Graphs.” <i>46th Annual ACM Symposium
    on Theory of Computing</i>, 674–683, Association for Computing Machinery, 2014,
    doi:<a href="https://doi.org/10.1145/2591796.2591869">10.1145/2591796.2591869</a>.
  short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 46th Annual ACM Symposium
    on Theory of Computing, Association for Computing Machinery, 2014.
conference:
  end_date: 2014-06-03
  location: New York, NY, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2014-05-31
date_created: 2022-08-16T09:41:57Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2024-11-06T12:20:12Z
day: '01'
doi: 10.1145/2591796.2591869
extern: '1'
external_id:
  arxiv:
  - '1504.07959'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1504.07959
month: '05'
oa: 1
oa_version: Preprint
publication: 46th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - 978-145032710-7
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sublinear-time decremental algorithms for single-source reachability and shortest
  paths on directed graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...