Approximating \(k\)-hop minimum-spanning trees
From MaRDI portal
Publication:2488210
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
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