Incremental algorithms for minimal length paths

DOI10.1016/0196-6774(91)90036-XMaRDI QIDQ3988824zbMATH OpenWikidataFDO

Authors Giuseppe F. Italiano, Giorgio Ausiello, Alberto Marchetti-Spaccamela, Umberto Nanni

Publication date 28 June 1992

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(91)90036-X

zbMATH Keywords

all pairs shortest paths problemAll pairs shortest paths problemedge costsedge insertions

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On-line computation of minimal and maximal length paths
• Dynamic algorithms for shortest paths in planar graphs
• scientific article; zbMATH DE number 30302
• scientific article; zbMATH DE number 219245
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

Cited in

(36)

• On-line computation of minimal and maximal length paths
• A uniform approach to semi-dynamic problems on digraphs
• NC algorithms for dynamically solving the all pairs shortest paths problem and related problems
• A fully dynamic algorithm for distributed shortest paths.
• Semi-dynamic breadth-first search in digraphs
• Disk-based shortest path discovery using distance index over large dynamic graphs
• Progressive simplification of polygonal curves
• An incremental linear-time learning algorithm for the optimum-path forest classifier
• Anytime search in dynamic graphs
• Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
• Fully dynamic all pairs shortest paths with real edge weights
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Algorithmic techniques for maintaining shortest routes in dynamic networks
• A survey on combinatorial optimization in dynamic environments
• Average case analysis of fully dynamic reachability for directed graphs
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Maintaining Longest Paths in Cyclic Graphs
• Path Minima in Incremental Unrooted Trees
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• scientific article; zbMATH DE number 30302 (Why is no real title available?)
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
• Semi-dynamic shortest paths and breadth-first search in digraphs
• Incremental single-source shortest paths in digraphs with arbitrary positive arc weights
• Average-Case Analysis of Online Topological Ordering
• Combinatorial Algorithms for Listing Paths in Minimal Change Order
• Maintaining longest paths incrementally
• Average case analysis of fully dynamic connectivity for directed graphs
• Counting edges in a dag
• Dynamic algorithms for shortest paths in planar graphs
• Fully dynamic algorithms for minimum weight cycle and related problems
• Lifelong planning \(\text{A}^*\)
• Maintaining longest paths incrementally
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• Average-case analysis of incremental topological ordering

This page was built for publication: Incremental algorithms for minimal length paths

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