Incremental single-source shortest paths in digraphs with arbitrary positive arc weights

DOI10.1016/j.tcs.2017.02.007zbMath1369.05091OpenAlexW2589286883WikidataQ62043091 ScholiaQ62043091MaRDI QIDQ528469

Ke Qiu, Wei Ding

Publication date: 12 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.02.007

zbMATH Keywords

random graphsedge deletiondynamic SSSPweight increase

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

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
• Worst-case update times for fully-dynamic all-pairs shortest paths
• An On-Line Edge-Deletion Problem
• Incremental algorithms for minimal length paths
• Paths in graphs
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Fibonacci heaps and their uses in improved network optimization algorithms
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Algorithm Theory - SWAT 2004
• A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
• 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: Incremental single-source shortest paths in digraphs with arbitrary positive arc weights