article

Approximating k-hop minimum-spanning trees

Authors:

Sariel Har-Peled,

Jochen KöNemann,

Edgar A. Ramos,

Martin SkutellaAuthors Info & Claims

Operations Research Letters, Volume 33, Issue 2

Pages 115 - 120

https://doi.org/10.1016/j.orl.2004.05.005

Published: 01 March 2005 Publication History

Abstract

Given a complete graph on~n nodes with metric edge costs, the minimum-costk-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most k edges. We present an algorithm that computes such a tree of total expected cost O(logn) times that of a minimum-cost k-hop spanning-tree.

References

[1]

Aardal, K.I., Chudak, F.A. and Shmoys, D.B., Improved approximation algorithms for the k-level facility location problem. Inform. Process. Lett. v72. 161-167.

Digital Library

[2]

Alfandari, L. and Paschos, V.T., Approximating minimum spanning tree of depth two. Int. Trans. Oper. Res. v6. 607-622.

[3]

Bar-Ilan, J., Kortsarz, G. and Peleg, D., Generalized submodular cover problems and applications. Theoret. Comput. Sci. v250 i1-2. 179-200.

[4]

Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, in: Proceedings, IEEE Symposium on Foundations of Computer Science, 1996, pp. 184-193.

Digital Library

[5]

Y. Bartal, On approximating arbitrary metrics by tree metrics, in: Proceedings, ACM Symposium on Theory of Computing, 1998, pp. 161-168.

Digital Library

[6]

Deering, S.E. and Cheriton, D.R., Multicast routing in datagram internetworks and extended LANs. ACM Trans. Comput. Syst. v8 i2. 85

[7]

S. Deering, D. Estrin, D. Farinacci, An architecture for wide-area multicast routing, in: Proceedings of SIGCOMM, 1994.

[8]

J. Fakcharoenphol, S. Rao, K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, in: Proceedings, ACM Symposium on Theory of Computing, 2003, pp. 448-455.

[9]

Gouveia, L. and Magnanti, T.L., Network flow models for designing diameter-constrained minimum-spanning and steiner trees. Networks. v41. 159-173.

[10]

Guha, S. and Khuller, S., Greedy strikes back: Improved facility location algorithms. . J. Algorithms. v31. 228-248.

Digital Library

[11]

Hassin, R. and Levin, A., Minimum spanning tree with hop restrictions. J. Algorithms. v48. 220-238.

Digital Library

[12]

Kompella, V.P., Pasquale, J.C. and Polyzos, G.C., Multicast routing for multimedia communication. IEEE/ACM Trans. Networks. v1 i3. 286-292.

[13]

G. Kortsarz, D. Peleg, Approximating the weight of shallow steiner trees, DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, Vol. 93, 1999.

[14]

M. Mahdian, Y. Ye, J. Zhang, A 1.52-approximation algorithm for the uncapacitated facility location problem, in: Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2002, pp. 127-137.

[15]

Marathe, M.V., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D.J. and Hunt III, H.B., Bicriteria network design problems. J. Algorithms. v28 i1. 142-171.

[16]

J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach, Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.

Cited By

Ghuge RNagarajan V(2022)Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design ProblemsMathematics of Operations Research10.1287/moor.2021.118147:2(1612-1630)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/moor.2021.1181
Lee JHwang JPark HKim D(2022)Ad Hoc Communication Topology Construction for Delay-Sensitive Internet of Vehicle ApplicationsWireless Communications & Mobile Computing10.1155/2022/82211792022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/8221179
Haeupler BHershkowitz DZuzic GKhuller SVassilevska Williams V(2021)Tree embeddings for hop-constrained network designProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451053(356-369)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451053
Show More Cited By

Approximating k-hop minimum-spanning trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Approximating k-hop minimum spanning trees in Euclidean metrics

In the minimum-cost k-hop spanning tree (k-hop MST) problem, we are given a set S of n points in a metric space, a positive small integer k and a root point r@?S. We are interested in computing a rooted spanning tree of minimum cost such that the ...
Degree-bounded minimum spanning trees

Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design

Given an undirected graph G = (V,E) with nonnegative costs on its edges, a root node r V, a set of demands D V with demand v D wishing to route w(v) units of flow (weight) to r, and a positive number k, the Capacitated Minimum Steiner Tree (CMStT) problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research Letters

Operations Research Letters Volume 33, Issue 2

March, 2005

113 pages

ISSN:0167-6377

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2004.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 March 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghuge RNagarajan V(2022)Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design ProblemsMathematics of Operations Research10.1287/moor.2021.118147:2(1612-1630)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/moor.2021.1181
Lee JHwang JPark HKim D(2022)Ad Hoc Communication Topology Construction for Delay-Sensitive Internet of Vehicle ApplicationsWireless Communications & Mobile Computing10.1155/2022/82211792022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/8221179
Haeupler BHershkowitz DZuzic GKhuller SVassilevska Williams V(2021)Tree embeddings for hop-constrained network designProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451053(356-369)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451053
Sharafeddine SJahed KFarhat ODawy Z(2017)Failure recovery in wireless content distribution networks with device-to-device cooperationComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.04.052128:C(108-122)Online publication date: 9-Dec-2017
https://dl.acm.org/doi/10.1016/j.comnet.2017.04.052
Panda BPushparaj Shetty D(2015)Strong minimum energy $$2$$2-hop rooted topology for hierarchical wireless sensor networksJournal of Combinatorial Optimization10.1007/s10878-013-9683-z30:4(1077-1094)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s10878-013-9683-z
Escoffier BGourvès LMonnot J(2013)Fair solutions for some multiagent optimization problemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-011-9188-z26:2(184-201)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1007/s10458-011-9188-z
Dinitz YElkin MSolomon S(2010)Low-Light Trees, and Tight Lower Bounds for Euclidean SpannersDiscrete & Computational Geometry10.5555/3116254.311632343:4(736-783)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.5555/3116254.3116323
Julstrom B(2010)Greedy heuristics for the bounded diameter minimum spanning tree problemACM Journal of Experimental Algorithmics10.1145/1498698.149869914(1.1-1.14)Online publication date: 5-Jan-2010
https://dl.acm.org/doi/10.1145/1498698.1498699
Sartori JKumar R(2010)Low-Overhead, high-speed multi-core barrier synchronizationProceedings of the 5th international conference on High Performance Embedded Architectures and Compilers10.1007/978-3-642-11515-8_4(18-34)Online publication date: 25-Jan-2010
https://dl.acm.org/doi/10.1007/978-3-642-11515-8_4
Kantor EPeleg D(2009)Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problemsJournal of Discrete Algorithms10.1016/j.jda.2008.11.0067:3(341-362)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.jda.2008.11.006
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents