scientific article; zbMATH DE number 7204496

DOI10.4230/LIPICS.ICALP.2017.44MaRDI QIDQ5111375zbMATH OpenFDO

Authors Aaron Bernstein

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1705.10097

zbMATH Keywords

shortest pathsdeterministic algorithmweighted graphdynamic algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Recommendations

• Deterministic partially dynamic single source shortest paths for sparse graphs
• Partially dynamic single-source shortest paths on digraphs with positive weights
• A single-source shortest path algorithm for dynamic graphs
• An algorithm for single-source shortest paths enumeration in parameterized weighted graphs
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• Approximate shortest paths in weighted graphs
• Shortest paths on dynamic graphs

Cited in

(8)

• Deterministic partially dynamic single source shortest paths for sparse graphs
• Partially dynamic maintenance of minimum weight hyperpaths
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Maintaining shortest paths under deletions in weighted directed graphs
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound

This page was built for publication:

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