Approximate distance oracles for graphs with dense clusters

DOI10.1016/J.COMGEO.2004.12.011MaRDI QIDQ883232zbMATH OpenOpenAlexFDO

Authors Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos

Publication date 4 June 2007

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://idus.us.es/xmlui/handle/11441/55008

zbMATH Keywords

computational geometrydistance oraclesgeometric networksshortest path queries

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Let \(H_1=(V,E_1)\) be a collection of \(N\) pairwise vertex disjoint \(O(1)\)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let \(H_2=(V,E_2)\) be the graph on \(V\) with \(M\) edges of non-negative weight. The union of the two graphs is denoted \(G=(V,E_1\cup E_2)\). The authors present a data structure of size \(O(M^2+n\log n)\) that answers \((1+\varepsilon)\)-approximate shortest path queries in \(G\) in constant time, where \(\varepsilon>0\) is constant.

Recommendations

• Algorithms and Computation
• scientific article; zbMATH DE number 2119744
• Approximate distance oracles
• Approximate distance oracles with constant query time
• Approximate distance oracles for geometric spanners

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A note on two problems in connexion with graphs
• All-Pairs Almost Shortest Paths
• An efficient algorithm for shortest paths in vertical and horizontal segments
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Approximate distance oracles
• Computing hierarchies of clusters from the Euclidean minimum spanning tree in linear time
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fibonacci heaps and their uses in improved network optimization algorithms
• Floats, Integers, and Single Source Shortest Paths
• scientific article; zbMATH DE number 1305410 (Why is no real title available?)
• scientific article; zbMATH DE number 1305420 (Why is no real title available?)
• scientific article; zbMATH DE number 1182917 (Why is no real title available?)
• scientific article; zbMATH DE number 1979513 (Why is no real title available?)
• scientific article; zbMATH DE number 2119744 (Why is no real title available?)
• scientific article; zbMATH DE number 910885 (Why is no real title available?)
• scientific article; zbMATH DE number 6469155 (Why is no real title available?)
• Optimal algorithms for complete linkage clustering in d dimensions
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Shortest paths in the plane with polygonal obstacles
• STACS 2005
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(4)

• Single point iterative weighted fuzzy C-means clustering algorithm for remote sensing image segmentation
• scientific article; zbMATH DE number 2119744 (Why is no real title available?)
• scientific article; zbMATH DE number 6469155 (Why is no real title available?)
• Algorithms and Computation

This page was built for publication: Approximate distance oracles for graphs with dense clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q883232)