---
_id: '11822'
abstract:
- lang: eng
  text: "The fully dynamic transitive closure problem asks to maintain reachability
    information in a directed graph between arbitrary pairs of vertices, while the
    graph undergoes a sequence of edge insertions and deletions. The problem has been
    thoroughly investigated in theory and many specialized algorithms for solving
    it have been proposed in the last decades. In two large studies [Frigioni ea,
    2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been
    evaluated experimentally against simple, static algorithms for graph traversal,
    showing the competitiveness and even superiority of the simple algorithms in practice,
    except for very dense random graphs or very high ratios of queries. A major drawback
    of those studies is that only small and mostly randomly generated graphs are considered.\r\nIn
    this paper, we engineer new algorithms to maintain all-pairs reachability information
    which are simple and space-efficient. Moreover, we perform an extensive experimental
    evaluation on both generated and real-world instances that are several orders
    of magnitude larger than those in the previous studies. Our results indicate that
    our new algorithms outperform all state-of-the-art algorithms on all types of
    input considerably in practice."
alternative_title:
- LIPIcs
article_number: '14'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
  full_name: Hanauer, Kathrin
  last_name: Hanauer
- 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: Christian
  full_name: Schulz, Christian
  last_name: Schulz
citation:
  ama: 'Hanauer K, Henzinger M, Schulz C. Faster fully dynamic transitive closure
    in practice. In: <i>18th International Symposium on Experimental Algorithms</i>.
    Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SEA.2020.14">10.4230/LIPIcs.SEA.2020.14</a>'
  apa: 'Hanauer, K., Henzinger, M., &#38; Schulz, C. (2020). Faster fully dynamic
    transitive closure in practice. In <i>18th International Symposium on Experimental
    Algorithms</i> (Vol. 160). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.4230/LIPIcs.SEA.2020.14">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>'
  chicago: Hanauer, Kathrin, Monika Henzinger, and Christian Schulz. “Faster Fully
    Dynamic Transitive Closure in Practice.” In <i>18th International Symposium on
    Experimental Algorithms</i>, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.SEA.2020.14">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>.
  ieee: K. Hanauer, M. Henzinger, and C. Schulz, “Faster fully dynamic transitive
    closure in practice,” in <i>18th International Symposium on Experimental Algorithms</i>,
    Pisa, Italy, 2020, vol. 160.
  ista: 'Hanauer K, Henzinger M, Schulz C. 2020. Faster fully dynamic transitive closure
    in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium
    on Experimental Algorithms, LIPIcs, vol. 160, 14.'
  mla: Hanauer, Kathrin, et al. “Faster Fully Dynamic Transitive Closure in Practice.”
    <i>18th International Symposium on Experimental Algorithms</i>, vol. 160, 14,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SEA.2020.14">10.4230/LIPIcs.SEA.2020.14</a>.
  short: K. Hanauer, M. Henzinger, C. Schulz, in:, 18th International Symposium on
    Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-09-09
  location: Pisa, Italy
  name: 'SEA: Symposium on Experimental Algorithms'
  start_date: 2020-09-07
date_created: 2022-08-12T07:32:53Z
date_published: 2020-06-12T00:00:00Z
date_updated: 2024-11-06T11:57:02Z
day: '12'
doi: 10.4230/LIPIcs.SEA.2020.14
extern: '1'
external_id:
  arxiv:
  - '2002.00813'
intvolume: '       160'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.SEA.2020.14
month: '06'
oa: 1
oa_version: Published Version
publication: 18th International Symposium on Experimental Algorithms
publication_identifier:
  isbn:
  - '9783959771481'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster fully dynamic transitive closure in practice
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 160
year: '2020'
...