TY - GEN

T1 - Shortest paths in euclidean graphs

AU - Sedgewick, Robert

AU - Vitter, Jeffrey Scott

N1 - Funding Information:
* Support for the first author was provided in part by NSF Grant MCS-83-08806. Support for the second author was provided in part by NSF Grant MCS-81-05324, by an IBM research contract, and by an IBM Faculty D e velopment Award, Support for this research was abo provided in part by oNR and DARpA under Contract I\rOOO14-83-K-0146 and ARPA Order No. 4786. Equip-ment support waa provided by NSF Grant MCS-81-218106.
Publisher Copyright:
© 1984 IEEE.

PY - 1984

Y1 - 1984

N2 - We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the running time of the algorithm to find the shortest path between a specified pair of vertices in a graph with V vertices and E edges is shown to be O(V) as compared with O (V log V + E) required by the classical (Dijkstra) algorithm.

AB - We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the running time of the algorithm to find the shortest path between a specified pair of vertices in a graph with V vertices and E edges is shown to be O(V) as compared with O (V log V + E) required by the classical (Dijkstra) algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85115262048&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115262048&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85115262048

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 417

EP - 424

BT - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984

PB - IEEE Computer Society

T2 - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984

Y2 - 24 October 1984 through 26 October 1984

ER -