Approximate distance oracles for graphs with dense clusters

DOI10.1016/J.COMGEO.2004.12.011zbMATH Open1144.65010OpenAlexW2116812387MaRDI QIDQ883232FDOQ883232

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

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

zbMATH Keywords

computational geometrydistance oraclesgeometric networksshortest path queries

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Algorithms and Computation
• Single point iterative weighted fuzzy C-means clustering algorithm for remote sensing image segmentation
• Title not available (Why is that?)
• Title not available (Why is that?)

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)