In this paper, we survey fully dynamic algorithms for path problems on general directed graphs. In particular, we consider two fundamental problems: dynamic transitive closure and dynamic shortest paths. Although research on these problems spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists.

Dynamic Shortest Paths and Transitive Closure: Algorithmic Techniques and Data Structures / Demetrescu, C; Italiano, Giuseppe Francesco. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 4:3(2006), pp. 353-383. [10.1016/j.jda.2005.12.003]

Dynamic Shortest Paths and Transitive Closure: Algorithmic Techniques and Data Structures

ITALIANO G
2006

Abstract

In this paper, we survey fully dynamic algorithms for path problems on general directed graphs. In particular, we consider two fundamental problems: dynamic transitive closure and dynamic shortest paths. Although research on these problems spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists.
Dynamic graph algorithms; Shortest paths
Dynamic Shortest Paths and Transitive Closure: Algorithmic Techniques and Data Structures / Demetrescu, C; Italiano, Giuseppe Francesco. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 4:3(2006), pp. 353-383. [10.1016/j.jda.2005.12.003]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/199813
Citazioni
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 13
social impact