The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
From MaRDI portal
Publication:3644728
DOI10.1007/978-3-642-03456-5_19zbMath1257.05053OpenAlexW2145057516MaRDI QIDQ3644728
Publication date: 12 November 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03456-5_19
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Metric spaces, metrizability (54E35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (8)
Truly Optimal Euclidean Spanners ⋮ Unnamed Item ⋮ Low-interference networks in metric spaces of bounded doubling dimension ⋮ The MST of symmetric disk graphs is light ⋮ Unnamed Item ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Metric Spaces with Expensive Distances
Cites Work
- Unnamed Item
- Unnamed Item
- An O(n log n) algorithm for the all-nearest-neighbors problem
- On sparse spanners of weighted graphs
- Approximating Euclidean distances by small degree graphs
- Lectures on analysis on metric spaces
- Computing the greedy spanner in near-quadratic time
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- Geometric Spanner Networks
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Computer Solutions of the Traveling Salesman Problem
This page was built for publication: The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
