Approximating \(k\)-hop minimum-spanning trees

DOI10.1016/j.orl.2004.05.005zbMath1099.90064OpenAlexW1991421283MaRDI QIDQ2488210

Sariel Har-Peled, Stefan Funke, Jochen Könemann, Ernst Althaus, Martin Skutella, Edgar A. Ramos

Publication date: 25 August 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.05.005

zbMATH Keywords

Approximation algorithmsDepth restrictionMetric space approximationMinimum spanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (16)

Finding bounded diameter minimum spanning tree in general graphs ⋮ On the bounded-hop MST problem on random Euclidean instances ⋮ SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Strong minimum energy \(2\)-hop rooted topology for hierarchical wireless sensor networks ⋮ A cost allocation rule for \(k\)-hop minimum cost spanning tree problems ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Approximating \(k\)-hop minimum spanning trees in Euclidean metrics ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Minimax flow tree problems ⋮ A new rule for source connection problems ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems ⋮ Network design for time‐constrained delivery ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics

Cites Work

• Unnamed Item
• Approximating the weight of shallow Steiner trees
• Generalized submodular cover problems and applications
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• Bicriteria Network Design Problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Minimum spanning tree with hop restrictions
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• A tight bound on approximating arbitrary metrics by tree metrics

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