---
_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 MH, 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. H., 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-10T09:10:26Z
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'
...
---
_id: '11786'
abstract:
- lang: eng
  text: "In this paper, we develop a dynamic version of the primal-dual method for
    optimization problems, and apply it to obtain the following results. (1) For the
    dynamic set-cover problem, we maintain an \U0001D442(\U0001D4532)-approximately
    optimal solution in \U0001D442(\U0001D453⋅log(\U0001D45A+\U0001D45B)) amortized
    update time, where \U0001D453 is the maximum “frequency” of an element, \U0001D45B
    is the number of sets, and \U0001D45A is the maximum number of elements in the
    universe at any point in time. (2) For the dynamic \U0001D44F-matching problem,
    we maintain an \U0001D442(1)-approximately optimal solution in \U0001D442(log3\U0001D45B)
    amortized update time, where \U0001D45B is the number of nodes in the graph."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- 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: Giuseppe F.
  full_name: Italiano, Giuseppe F.
  last_name: Italiano
citation:
  ama: 'Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via
    primal-dual method. In: <i>42nd International Colloquium on Automata, Languages
    and Programming</i>. Vol 9134. Springer Nature; 2015:206-218. doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_17">10.1007/978-3-662-47672-7_17</a>'
  apa: 'Bhattacharya, S., Henzinger, M. H., &#38; Italiano, G. F. (2015). Design of
    dynamic algorithms via primal-dual method. In <i>42nd International Colloquium
    on Automata, Languages and Programming</i> (Vol. 9134, pp. 206–218). Kyoto, Japan:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-662-47672-7_17">https://doi.org/10.1007/978-3-662-47672-7_17</a>'
  chicago: Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design
    of Dynamic Algorithms via Primal-Dual Method.” In <i>42nd International Colloquium
    on Automata, Languages and Programming</i>, 9134:206–18. Springer Nature, 2015.
    <a href="https://doi.org/10.1007/978-3-662-47672-7_17">https://doi.org/10.1007/978-3-662-47672-7_17</a>.
  ieee: S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Design of dynamic algorithms
    via primal-dual method,” in <i>42nd International Colloquium on Automata, Languages
    and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.
  ista: 'Bhattacharya S, Henzinger MH, Italiano GF. 2015. Design of dynamic algorithms
    via primal-dual method. 42nd International Colloquium on Automata, Languages and
    Programming. ICALP: International Colloquium on Automata, Languages, and Programming,
    LNCS, vol. 9134, 206–218.'
  mla: Bhattacharya, Sayan, et al. “Design of Dynamic Algorithms via Primal-Dual Method.”
    <i>42nd International Colloquium on Automata, Languages and Programming</i>, vol.
    9134, Springer Nature, 2015, pp. 206–18, doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_17">10.1007/978-3-662-47672-7_17</a>.
  short: S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium
    on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218.
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-11T09:28:49Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-10T09:13:31Z
day: '01'
doi: 10.1007/978-3-662-47672-7_17
extern: '1'
external_id:
  arxiv:
  - '1604.05337'
intvolume: '      9134'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1604.05337
month: '01'
oa: 1
oa_version: Preprint
page: 206 - 218
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: Design of dynamic algorithms via primal-dual method
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...
---
_id: '11787'
abstract:
- lang: eng
  text: "We present faster algorithms for computing the 2-edge and 2-vertex strongly
    connected components of a directed graph. While in undirected graphs the 2-edge
    and 2-vertex connected components can be found in linear time, in directed graphs
    with m edges and n vertices only rather simple O(m n)-time algorithms were known.
    We use a hierarchical sparsification technique to obtain algorithms that run in
    time \U0001D442(\U0001D45B2). For 2-edge strongly connected components our algorithm
    gives the first running time improvement in 20 years. Additionally we present
    an \U0001D442(\U0001D45A2/log\U0001D45B)-time algorithm for 2-edge strongly connected
    components, and thus improve over the O(m n) running time also when \U0001D45A=\U0001D442(\U0001D45B).
    Our approach extends to k-edge and k-vertex strongly connected components for
    any constant k with a running time of \U0001D442(\U0001D45B2log\U0001D45B) for
    k-edge-connectivity and \U0001D442(\U0001D45B3) for k-vertex-connectivity."
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: Veronika
  full_name: Loitzenbauer, Veronika
  last_name: Loitzenbauer
citation:
  ama: 'Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly
    connected components in quadratic time. In: <i>2nd International Colloquium on
    Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:713-724.
    doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_58">10.1007/978-3-662-47672-7_58</a>'
  apa: 'Henzinger, M. H., Krinninger, S., &#38; Loitzenbauer, V. (2015). Finding 2-edge
    and 2-vertex strongly connected components in quadratic time. In <i>2nd International
    Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 713–724).
    Kyoto, Japan: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-47672-7_58">https://doi.org/10.1007/978-3-662-47672-7_58</a>'
  chicago: Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding
    2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In <i>2nd
    International Colloquium on Automata, Languages and Programming</i>, 9134:713–24.
    Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-47672-7_58">https://doi.org/10.1007/978-3-662-47672-7_58</a>.
  ieee: M. H. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex
    strongly connected components in quadratic time,” in <i>2nd International Colloquium
    on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp.
    713–724.
  ista: 'Henzinger MH, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex
    strongly connected components in quadratic time. 2nd International Colloquium
    on Automata, Languages and Programming. ICALP: International Colloquium on Automata,
    Languages, and Programming, LNCS, vol. 9134, 713–724.'
  mla: Henzinger, Monika H., et al. “Finding 2-Edge and 2-Vertex Strongly Connected
    Components in Quadratic Time.” <i>2nd International Colloquium on Automata, Languages
    and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 713–24, doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_58">10.1007/978-3-662-47672-7_58</a>.
  short: M.H. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium
    on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724.
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-11T09:38:34Z
date_published: 2015-07-06T00:00:00Z
date_updated: 2023-02-10T09:21:47Z
day: '06'
doi: 10.1007/978-3-662-47672-7_58
extern: '1'
external_id:
  arxiv:
  - '1412.6466'
intvolume: '      9134'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1412.6466
month: '07'
oa: 1
oa_version: Preprint
page: 713 - 724
publication: 2nd 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: Finding 2-edge and 2-vertex strongly connected components in quadratic time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...