Approximating k-hop minimum spanning trees in Euclidean metrics
From MaRDI portal
(Redirected from Publication:963410)
Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
Recommendations
- Approximating \(k\)-hop minimum-spanning trees
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
- A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
- scientific article; zbMATH DE number 2079416
- Computing a (1+)-approximate geometric minimum-diameter spanning tree
- Minimum spanning trees for tree metrics: Abridgements and adjustments
- Lower bounds for testing Euclidean minimum spanning trees
Cites work
- A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- A tight bound on approximating arbitrary metrics by tree metrics
- Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems
- Approximating \(k\)-hop minimum-spanning trees
- Approximating the two-level facility location problem via a quasi-greedy approach
- Greedy Strikes Back: Improved Facility Location Algorithms
- scientific article; zbMATH DE number 1947060 (Why is no real title available?)
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Structural Information and Communication Complexity
Cited in
(13)- Bounded-hop communication networks
- Resilient \(k\)-d trees: \(k\)-means in space revisited
- Minimizing the sum of distances to a server in a constraint network
- On the bounded-hop MST problem on random Euclidean instances
- Approximating \(k\)-hop minimum-spanning trees
- On the bounded-hop range assignment problem
- Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree
- Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Structural Information and Communication Complexity
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- A PTAS for k-hop MST on the Euclidean plane: improving dependency on k
- Low-light trees, and tight lower bounds for Euclidean spanners
This page was built for publication: Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963410)
