Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs

DOI10.1007/978-3-319-26626-8_39zbMath1478.05135OpenAlexW2394850749MaRDI QIDQ3467869

Wei Ding, Ke Qiu

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_39

zbMATH Keywords

random graphedge deletiondynamic SSSPweight increase

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Distance in graphs (05C12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths
• An On-Line Edge-Deletion Problem
• Incremental algorithms for minimal length paths
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Partially Dynamic Single-Source Shortest Paths on Digraphs with Positive Weights
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Algorithm Theory - SWAT 2004
• All-Pairs Shortest Paths in $O(n^2)$ time with high probability
• A new approach to dynamic all pairs shortest paths
• Algorithms – ESA 2004
• Maintaining shortest paths under deletions in weighted directed graphs
• Random Graphs

This page was built for publication: Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs