Faster algorithms for the shortest path problem
From MaRDI portal
Publication:3474275
DOI10.1145/77600.77615zbMath0696.68046WikidataQ55923156 ScholiaQ55923156MaRDI QIDQ3474275
Ravindra K. Ahuja, James B. Orlin, Kurt Mehlhorn, Robert Endre Tarjan
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/47994
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68P05: Data structures
Related Items
Maximum weightk-independent set problem on permutation graphs, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, Unnamed Item, Faster shortest-path algorithms for planar graphs, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, A linear time algorithm for the maximum capacity path problem, An improved Dijkstra's shortest path algorithm for sparse network, A double scaling algorithm for the constrained maximum flow problem, Weighted fusion graphs: Merging properties and watersheds, The k most vital arcs in the shortest path problem, The suffix tree of a tree and minimizing sequential transducers, On graphs preserving rectilinear shortest paths in the presence of obstacles, Computing the optimal IO sequences of a protocol in polynomial time, Shortest path algorithms: A computational study with the C programming language, An optimal algorithm for the period of a strongly connected digraph, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, On the exponent of all pairs shortest path problem, On fast planning of suboptimal paths amidst polygonal obstacles in plane, Minimization algorithms for sequential transducers, Semi-dynamic breadth-first search in digraphs, An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs, Theory of 2-3 heaps, A new approach to all-pairs shortest paths on real-weighted graphs, All-pairs shortest paths and the essential subgraph, Shortest paths algorithms: Theory and experimental evaluation, A sequential algorithm for finding a maximum weightK-independent set on interval graphs, Rank-Sensitive Priority Queues, Unnamed Item, Competitive Algorithms for Layered Graph Traversal, Finding the k Shortest Paths
