We show how to maintain a shortest path tree of a general directed graph G with unit edge weights and n vertices, during a sequence of edge deletions or a sequence of edge insertions, in O(n) amortized time per operation using linear space. Distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path. These results are extended to the case of integer edge weights in [1, C], with a bound of O(Cn) amortized time per operation. We also show how to maintain a breadth-first search tree of a directed graph G in an incremental or a decremental setting in O(n) amortized time per operation using linear space.
Semi-dynamic shortest paths and breadth-first search in digraphs / Franciosa, Paolo Giulio; Daniele, Frigioni; Roberto, Giaccio. - STAMPA. - 1200:(1997), pp. 33-46. (Intervento presentato al convegno 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS 97) tenutosi a LUBECK, GERMANY nel FEB 27-MAR 01, 1997) [10.1007/bfb0023446].
Semi-dynamic shortest paths and breadth-first search in digraphs
FRANCIOSA, Paolo Giulio;
1997
Abstract
We show how to maintain a shortest path tree of a general directed graph G with unit edge weights and n vertices, during a sequence of edge deletions or a sequence of edge insertions, in O(n) amortized time per operation using linear space. Distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path. These results are extended to the case of integer edge weights in [1, C], with a bound of O(Cn) amortized time per operation. We also show how to maintain a breadth-first search tree of a directed graph G in an incremental or a decremental setting in O(n) amortized time per operation using linear space.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.