Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
From MaRDI portal
Publication:963410
DOI10.1016/j.ipl.2008.01.004zbMath1186.68562MaRDI QIDQ963410
Publication date: 19 April 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2008.01.004
Related Items
Low-light trees, and tight lower bounds for Euclidean spanners, Bounded-hop communication networks, Minimizing the sum of distances to a server in a constraint network, On the Bounded-Hop Range Assignment Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
- Approximating \(k\)-hop minimum-spanning trees
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- Greedy Strikes Back: Improved Facility Location Algorithms
- Structural Information and Communication Complexity
- A tight bound on approximating arbitrary metrics by tree metrics