A single-source shortest path algorithm for dynamic graphs

DOI10.1016/J.AKCEJ.2020.01.002MaRDI QIDQ4956230zbMATH OpenOpenAlexFDO

Authors Muteb Alshammari, Abdelmounaam Rezgui

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.akcej.2020.01.002

zbMATH Keywords

shortest pathsdynamic graphsSSSP

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• An all pairs shortest path algorithm for dynamic graphs
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• A novel single source shortest path algorithm
• scientific article; zbMATH DE number 7266346
• Shortest-path algorithms and dynamic cost changes

Cites work

• scientific article; zbMATH DE number 871917 (Why is no real title available?)
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• An all pairs shortest path algorithm for dynamic graphs
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• On the computational complexity of dynamic graph problems
• Power balance and apportionment algorithms for the United States Congress
• Shortest Path Tree Computation in Dynamic Graphs

Cited in

(13)

• An all pairs shortest path algorithm for dynamic graphs
• Shortest Path Tree Computation in Dynamic Graphs
• scientific article; zbMATH DE number 7204496 (Why is no real title available?)
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide
• The improved sliding shortest path algorithm
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• Computing source-to-target shortest paths for complex networks in RDBMS
• Disk-based shortest path discovery using distance index over large dynamic graphs
• Locality-based relaxation: an efficient method for GPU-based computation of shortest paths
• A novel single source shortest path algorithm
• An algorithmic framework for the single source shortest path problem with applications to disk graphs
• Boosting the exploration of huge dynamic graphs

This page was built for publication: A single-source shortest path algorithm for dynamic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956230)