Efficient Algorithms for Shortest Paths in Sparse Networks

From MaRDI portal
Publication:4111093


DOI10.1145/321992.321993zbMath0343.68028WikidataQ56484789 ScholiaQ56484789MaRDI QIDQ4111093

Donald B. Johnson

Publication date: 1977

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321992.321993


68Q25: Analysis of algorithms and problem complexity

05C20: Directed graphs (digraphs), tournaments

68N01: General topics in the theory of software

68W99: Algorithms in computer science


Related Items

Unnamed Item, Unnamed Item, Efficient parallel algorithms for computing all pair shortest paths in directed graphs, A multiple-heaps algorithm for parallel simulation of collision systems, The distributed simulation of clustered processes, Minmax regret location--allocation problem on a network under uncertainty, Two fast algorithms for all-pairs shortest paths, A distributed shortest path algorithm for a planar network, Retiming synchronous circuitry, Scaling algorithms for network problems, A heuristic for the p-center problem in graphs, An O(m log D) algorithm for shortest paths, A new algorithm to find the shortest paths between all pairs of nodes, Topological design of telecommunication networks --- local access design methods, On an instance of the inverse shortest paths problem, On the expected behaviors of the Dijkstra's shortest path algorithm for complete graphs, On the use of an inverse shortest paths algorithm for recovering linearly correlated costs, Exact solutions for the construction of optimal length test sequences, A hybrid algorithm for the shortest path between two nodes in the presence of few negative arcs, A new approach to all-pairs shortest paths on real-weighted graphs, All-pairs shortest paths and the essential subgraph, Computation of shortest path in cellular automata, All-pairs-shortest-length on strongly chordal graphs, Synchronization paradigm for protocol testing under multiparty configuration, Efficient transitive closure of sparse matrices over closed semirings, Planar graphs, negative weight edges, shortest paths, and near linear time, Rectilinear paths among rectilinear obstacles, A quick method for finding shortest pairs of disjoint paths, Shortest-path algorithms: Taxonomy and annotation, A priority queue in which initialization and queue operations takeO(loglogD) time, A Dijkstra-like shortest path algorithm for certain cases of negative arc lengths, An efficient algorithm for K shortest simple paths, Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem, Unnamed Item, Optimally fast shortest path algorithms for some classes of graphs