Shortest paths in Euclidean graphs

DOI10.1007/BF01840435zbMath0611.68044OpenAlexW2077383738MaRDI QIDQ1087335

Jeffrey Scott Vitter, Robert Sedgewick

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840435

zbMATH Keywords

graph algorithmanalysis of algorithmspriority queueDijkstra's algorithm

Mathematics Subject Classification ID

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

Related Items (17)

Bidirectional A* search on time-dependent road networks ⋮ Generating sparse spanners for weighted graphs ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ An O(NP) sequence comparison algorithm ⋮ Solving k-shortest and constrained shortest path problems efficiently ⋮ A parallel bio-inspired shortest path algorithm ⋮ A more realistic approach for airport ground movement optimisation with stand holding ⋮ Classes of graphs which approximate the complete Euclidean graph ⋮ On sparse spanners of weighted graphs ⋮ Shortest-path queries in static networks ⋮ Heuristic shortest path algorithms for transportation applications: state of the art ⋮ An efficient algorithm for facility location in the presence of forbidden regions ⋮ Shortest paths on dynamic graphs ⋮ A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS ⋮ A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing ⋮ Time-dependent shortest paths through a fixed sequence of nodes: application to a travel planning problem ⋮ A shortest-path algorithm for Manhattan graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Oriented percolation in two dimensions
• Faster methods for random sampling
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Shortest paths with euclidean distances: An explanatory model
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: Shortest paths in Euclidean graphs