Fully dynamic algorithms for maintaining shortest paths trees

被引:124
|
作者
Frigioni, D
Marchetti-Spaccamela, A
Nanni, U
机构
[1] Univ Aquila, Dipartimento Ingn Elettr, I-67040 Laquila, Italy
[2] Univ Rome, Dipartimento Informat & Sistemist, I-00198 Rome, Italy
[3] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, I-00198 Rome, Italy
来源
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2000年 / 34卷 / 02期
关键词
D O I
10.1006/jagm.1999.1048
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance from the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the weights of edges, then the update procedures require O(log n) worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded arboricity, bounded degree, bounded treewidth, and bounded pagenumber. For general graphs with n vertices and m edges the algorithms require O(root m log n) worst case time per output update. We also show that, if insertions and deletions of edges are allowed, then similar amortized bounds hold. (C) 2000 Academic Press.
引用
收藏
页码:251 / 281
页数:31
相关论文
共 50 条
  • [21] Trans-dichotomous algorithms for minimum spanning trees and shortest paths
    Fredman, Michael L., 1600, Academic Press Inc, San Diego, CA, United States (48):
  • [22] Partially Disjoint Shortest Paths and Near-Shortest Paths Trees
    Dinitz, Yefim
    Dolev, Iomi
    Kumar, Manish
    Schieber, Baruch
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2024, 2025, 14931 : 240 - 254
  • [23] Maintaining centdians in a fully dynamic forest with top trees
    Wang, Hung-Lung
    DISCRETE APPLIED MATHEMATICS, 2015, 181 : 310 - 315
  • [24] Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks
    Davies, C
    Lingras, P
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 144 (01) : 27 - 38
  • [25] Partially Dynamic Algorithms for Distributed Shortest Paths and their Experimental Evaluation
    Cicerone, Serafino
    D'Angelo, Gianlorenzo
    Di Stefano, Gabriele
    Frigioni, Daniele
    Petricola, Alberto
    JOURNAL OF COMPUTERS, 2007, 2 (09) : 16 - 26
  • [26] Partially dynamic algorithms for distributed shortest paths and their experimental evaluation
    Dipartimento di Ingegneria Elettrica e dell'Informazione, Università dell'Aquila, I-67040 Monteluco di Roio, L'Aquila, Italy
    J. Comput., 2007, 9 (16-26):
  • [27] Fully dynamic all pairs shortest paths with real edge weights
    Demetrescu, Camil
    Italiano, Giuseppe F.
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2006, 72 (05) : 813 - 837
  • [28] TRANS-DICHOTOMOUS ALGORITHMS FOR MINIMUM SPANNING-TREES AND SHORTEST PATHS
    FREDMAN, ML
    WILLARD, DE
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (03) : 533 - 551
  • [29] Fully dynamic all pairs shortest paths with real edge weights
    Demetrescu, C
    Italiano, GF
    42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, : 260 - 267
  • [30] Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
    Baswana, Surender
    Hariharan, Ramesh
    Sen, Sandeep
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2007, 62 (02): : 74 - 92