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

DOI10.1016/J.TCS.2017.02.007MaRDI QIDQ528469zbMATH OpenOpenAlexWikidataFDO

Authors Wei Ding, Ke Qiu

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

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

Recommendations

• Partially dynamic single-source shortest paths on digraphs with positive weights
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• Semidynamic algorithms for maintaining single-source shortest path trees
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A new approach to dynamic all pairs shortest paths
• A note on two problems in connexion with graphs
• A subquadratic-time algorithm for decremental single-source shortest paths
• Algorithm Theory - SWAT 2004
• Algorithms – ESA 2004
• An On-Line Edge-Deletion Problem
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
• Fibonacci heaps and their uses in improved network optimization algorithms
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions
• Incremental algorithms for minimal length paths
• Maintaining shortest paths under deletions in weighted directed graphs
• Paths in graphs
• Random Graphs
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths

Cited in

(3)

• Shortest paths in a diagraph with an underestimated arc weight
• Partially dynamic single-source shortest paths on digraphs with positive weights
• Dynamic single-source shortest paths in Erdős-Rényi random graphs

This page was built for publication: Incremental single-source shortest paths in digraphs with arbitrary positive arc weights

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