Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
type: Item
instance of: scholarly article
title: Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
zbMATH Open document ID: 1186.68562
author: Sören Laue
author: Domagoj Matijević
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5694961
zbMATH Keywords: approximation algorithms
zbMATH Keywords: minimum spanning trees
zbMATH Keywords: depth restriction
MaRDI profile type: Publication
full work available at URL: j.ipl.2008.01.004
OpenAlex ID: W2039405536
cites work: A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
cites work: Approximating \(k\)-hop minimum-spanning trees
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: Q4542527
cites work: Structural Information and Communication Complexity
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Greedy Strikes Back: Improved Facility Location Algorithms
cites work: Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems
cites work: A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
cites work: Q4411290
cites work: Q5501342
DOI: 10.1016/J.IPL.2008.01.004
Recommended article: Approximating \(k\)-hop minimum-spanning trees
Recommended article: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
Recommended article: Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
Recommended article: A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees
Recommended article: Q4471376
Recommended article: Time-space trade-offs for computing Euclidean minimum spanning trees
Recommended article: Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree
Recommended article: Minimum spanning trees for tree metrics: Abridgements and adjustments
Recommended article: Lower bounds for testing Euclidean minimum spanning trees
description: scientific article; zbMATH DE number 5694961