---
_id: '11785'
abstract:
- lang: eng
  text: "Recently we presented the first algorithm for maintaining the set of nodes
    reachable from a source node in a directed graph that is modified by edge deletions
    with \U0001D45C(\U0001D45A\U0001D45B) total update time, where \U0001D45A is the
    number of edges and \U0001D45B is the number of nodes in the graph [Henzinger
    et al. STOC 2014]. The algorithm is a combination of several different algorithms,
    each for a different \U0001D45A vs. \U0001D45B trade-off. For the case of \U0001D45A=Θ(\U0001D45B1.5)
    the running time is \U0001D442(\U0001D45B2.47), just barely below \U0001D45A\U0001D45B=Θ(\U0001D45B2.5).
    In this paper we simplify the previous algorithm using new algorithmic ideas and
    achieve an improved running time of \U0001D442̃ (min(\U0001D45A7/6\U0001D45B2/3,\U0001D45A3/4\U0001D45B5/4+\U0001D45C(1),\U0001D45A2/3\U0001D45B4/3+\U0001D45C(1)+\U0001D45A3/7\U0001D45B12/7+\U0001D45C(1))).
    This gives, e.g., \U0001D442(\U0001D45B2.36) for the notorious case \U0001D45A=Θ(\U0001D45B1.5).
    We obtain the same upper bounds for the problem of maintaining the strongly connected
    components of a directed graph undergoing edge deletions. Our algorithms are correct
    with high probabililty against an oblivious adversary."
alternative_title:
- LNCS
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. Improved algorithms for decremental
    single-source reachability on directed graphs. In: <i>42nd International Colloquium
    on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:725-736.
    doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_59">10.1007/978-3-662-47672-7_59</a>'
  apa: 'Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2015). Improved algorithms
    for decremental single-source reachability on directed graphs. In <i>42nd International
    Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 725–736).
    Kyoto, Japan: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-47672-7_59">https://doi.org/10.1007/978-3-662-47672-7_59</a>'
  chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Improved
    Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In
    <i>42nd International Colloquium on Automata, Languages and Programming</i>, 9134:725–36.
    Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-47672-7_59">https://doi.org/10.1007/978-3-662-47672-7_59</a>.
  ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental
    single-source reachability on directed graphs,” in <i>42nd International Colloquium
    on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp.
    725–736.
  ista: 'Henzinger M, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental
    single-source reachability on directed graphs. 42nd International Colloquium on
    Automata, Languages and Programming. ICALP: International Colloquium on Automata,
    Languages, and Programming, LNCS, vol. 9134, 725–736.'
  mla: Henzinger, Monika, et al. “Improved Algorithms for Decremental Single-Source
    Reachability on Directed Graphs.” <i>42nd International Colloquium on Automata,
    Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 725–36, doi:<a
    href="https://doi.org/10.1007/978-3-662-47672-7_59">10.1007/978-3-662-47672-7_59</a>.
  short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium
    on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736.
conference:
  end_date: 2015-07-10
  location: Kyoto, Japan
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2015-07-06
date_created: 2022-08-11T08:51:32Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2024-11-06T12:10:50Z
day: '01'
doi: 10.1007/978-3-662-47672-7_59
extern: '1'
external_id:
  arxiv:
  - '1612.03856'
intvolume: '      9134'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1612.03856
month: '01'
oa: 1
oa_version: Preprint
page: 725 - 736
publication: 42nd International Colloquium on Automata, Languages and Programming
publication_identifier:
  isbn:
  - '9783662476710'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved algorithms for decremental single-source reachability on directed
  graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...