Fully dynamic shortest paths in digraphs with arbitrary arc weights

DOI10.1016/S0196-6774(03)00082-8zbMath1064.68068MaRDI QIDQ4820906

Alberto Marchetti-Spaccamela, Daniele Frigioni, Umberto Nanni

Publication date: 1 October 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

output complexityzero-length cycles

Mathematics Subject Classification ID

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

Related Items

Anytime search in dynamic graphs ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ Single backup table schemes for shortest-path routing ⋮ Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates ⋮ Improved Dynamic Graph Coloring ⋮ Dynamically Maintaining Shortest Path Trees under Batches of Updates