Approximate distance oracles for graphs with dense clusters

DOI10.1016/j.comgeo.2004.12.011zbMath1144.65010OpenAlexW2116812387MaRDI QIDQ883232

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)

Related Items

Single point iterative weighted fuzzy C-means clustering algorithm for remote sensing image segmentation

Cites Work

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