Approximating \(k\)-hop minimum spanning trees in Euclidean metrics

DOI10.1016/j.ipl.2008.01.004zbMath1186.68562OpenAlexW2039405536MaRDI QIDQ963410

Domagoj Matijević, Sören Laue

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

zbMATH Keywords

approximation algorithmsminimum spanning treesdepth restriction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (6)

On the Bounded-Hop Range Assignment Problem ⋮ Bounded-hop communication networks ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Minimizing the sum of distances to a server in a constraint network ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating \(k\)-hop minimum spanning trees in Euclidean metrics