Semidynamic algorithms for maintaining single-source shortest path trees

DOI10.1007/PL00009224zbMath0915.68083MaRDI QIDQ1273931

Daniele Frigioni, Umberto Nanni, Alberto Marchetti-Spaccamela

Publication date: 22 June 1999

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

amortized complexitysingle-source shortest path tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (13)

Fully-Dynamic Approximation of Betweenness Centrality ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ A fully dynamic algorithm for distributed shortest paths. ⋮ Minimize the maximum duty in multi-interface networks ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ Min-Max Coverage in Multi-interface Networks ⋮ Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates ⋮ Semi-dynamic breadth-first search in digraphs ⋮ Approximating Betweenness Centrality in Fully Dynamic Networks ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks ⋮ Dynamically Maintaining Shortest Path Trees under Batches of Updates ⋮ Lifelong planning \(\text{A}^*\)

This page was built for publication: Semidynamic algorithms for maintaining single-source shortest path trees