Efficient Algorithms for Shortest Paths in Sparse Networks

DOI10.1145/321992.321993zbMath0343.68028OpenAlexW2022980325WikidataQ56484789 ScholiaQ56484789MaRDI QIDQ4111093

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Labeled shortest paths in digraphs with negative and positive edge weights, Examining k-nearest neighbour networks: Superfamily phenomena and inversion, Successful network inference from time-series data using mutual information rate, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, An edge scanning method for the continuous deviation‐flow refueling station location problem on a general network, Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND, A novel approach for modeling order picking paths, A novel pseudo‐polynomial approach for shortest path problems, Online learning of energy consumption for navigation of electric vehicles, Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages, Computational complexity of the original and extended diophantine Frobenius problem, Parameterized complexity of diameter, Unnamed Item, Unnamed Item, Unnamed Item, A novel algorithm for clearing financial obligations between companies - An application within the Romanian Ministry of economy, Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time, A lexicographic optimization approach to the deviation-flow refueling station location problem on a general network, Scaling algorithms for network problems, Balancing Geometry and Density: Path Distances on High-Dimensional Data, The geodesic distance on the generalized gamma manifold for texture image retrieval, Exact solutions for the construction of optimal length test sequences, Efficient transitive closure of sparse matrices over closed semirings, A new approach to all-pairs shortest paths on real-weighted graphs, Solving the all-pairs-shortest-length problem on chordal bipartite graphs, Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time, A survey of the all-pairs shortest paths problem and its variants in graphs, Unnamed Item, Weighted \(A^*\) search - unifying view and application, All-pairs shortest paths and the essential subgraph, A heuristic for the p-center problem in graphs, Faster All-Pairs Shortest Paths via Circuit Complexity, Minmax regret location--allocation problem on a network under uncertainty, Correlation between weighted spectral distribution and average path length in evolving networks, Truncated metric dimension for finite graphs, Computation of shortest path in cellular automata, Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem, Solving all-pairs shortest path by single-source computations: theory and practice, Two fast algorithms for all-pairs shortest paths, All-pairs-shortest-length on strongly chordal graphs, Two-level heaps: a new priority queue structure with applications to the single source shortest path problem, Power-Law Noises over General Spatial Domains and on Nonstandard Meshes, Efficiently Listing Bounded Length st-Paths, Fast query structures in anisotropic media, Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs, Approximability results for the converse connectedp-centre problem^†, An O(m log D) algorithm for shortest paths, Depth-based complexity traces of graphs, Approximate shortest paths in weighted graphs, Crossover can provably be useful in evolutionary computation, Unnamed Item, A new algorithm to find the shortest paths between all pairs of nodes, A distributed shortest path algorithm for a planar network, Retiming synchronous circuitry, Synchronization paradigm for protocol testing under multiparty configuration, Universal construction mechanism for networks from one-dimensional symbol sequences, An all-pairs shortest path algorithm for bipartite graphs, Topological design of telecommunication networks --- local access design methods, Exact solution approaches for the discrete lot-sizing and scheduling problem with parallel resources, Incremental closure for systems of two variables per inequality, Polynomial-time proofs that groups are hyperbolic, Spreading dynamics in complex networks, Generating realistic labelled, weighted random graphs, On an instance of the inverse shortest paths problem, Faster separation of 1-wheel inequalities by graph products, Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem, Efficient parallel algorithms for computing all pair shortest paths in directed graphs, Dynamic conditional value-at-risk model for routing and scheduling of hazardous material transportation networks, The windy rural postman problem with a time-dependent zigzag option, Quickest path queries on transportation network, The electric location routing problem with time windows and partial recharging, Analyzing the stock market based on the structure of \textit{kNN} network, A language for generic programming in the large, A quick method for finding shortest pairs of disjoint paths, Shortest-path algorithms: Taxonomy and annotation, A multiple-heaps algorithm for parallel simulation of collision systems, Shortest-path queries in static networks, Planar graphs, negative weight edges, shortest paths, and near linear time, A spectral approach to the shortest path problem, Ranking the spreading ability of nodes in complex networks based on local structure, Solving path problems on the GPU, Path optimization with limited sensing ability, On covering by translates of a set, A matrix-based approach to searching colored paths in a weighted colored multidigraph, Convolutional wasserstein distances, Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs, On the expected behaviors of the Dijkstra's shortest path algorithm for complete graphs, Resilient capacity-aware routing, Identifying and ranking influential spreaders in complex networks by combining a local-degree sum and the clustering coefficient, A Dijkstra-like shortest path algorithm for certain cases of negative arc lengths, An efficient implementation of an algorithm for findingK shortest simple paths, Optimal path discovery problem with homogeneous knowledge, Single-source shortest paths and strong connectivity in dynamic planar graphs, Solving the Nearly Symmetric All-Pairs Shortest-Path Problem, Energy-optimal routes for battery electric vehicles, The distributed simulation of clustered processes, Efficient reconstruction of metabolic pathways by bidirectional chemical search, What's decidable about weighted automata?, A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS, Faster algorithms for shortest path and network flow based on graph decomposition, Rectilinear paths among rectilinear obstacles, A hybrid algorithm for the shortest path between two nodes in the presence of few negative arcs, Incremental distance products via faulty shortest paths, Unnamed Item, Unnamed Item, A Survey on Priority Queues, Unnamed Item, Nonlocal pagerank, Network inference combining mutual information rate and statistical tests, A priority queue in which initialization and queue operations takeO(loglogD) time, The grid based approach, a fast local evaluation technique for line planning, From Circuit Complexity to Faster All-Pairs Shortest Paths, Optimally fast shortest path algorithms for some classes of graphs, Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time, On the use of an inverse shortest paths algorithm for recovering linearly correlated costs, An efficient algorithm for K shortest simple paths, Fast algorithms for the undirected negative cost cycle detection problem