IEEE - Institute of Electrical and Electronics Engineers, Inc. - Approximate Shortest Path Queries in Graphs Using Voronoi Duals

2009 Sixth International Symposium on Voronoi Diagrams (ISVD)

Author(s): Honiden, S. ; Houle, M.E. ; Sommer, C. ; Wolff, M.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 June 2009
Conference Location: Copenhagen, Denmark, Denmark
Conference Date: 23 June 2009
Page(s): 53 - 62
ISBN (CD): 978-0-7695-3781-8
ISBN (Paper): 978-1-4244-4769-5
DOI: 10.1109/ISVD.2009.30
Regular:

We propose an approximation method to answer point-to-point shortest path queries in undirected graphs, based on random sampling and Voronoi duals. We compute a simplification of the graph by... View More

Advertisement