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

DOI10.1016/J.TCS.2017.02.007zbMATH Open1369.05091OpenAlexW2589286883WikidataQ62043091 ScholiaQ62043091MaRDI QIDQ528469FDOQ528469

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

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

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)

Cites Work

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

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)