Abstract
A tree cover is a collection of subtrees of a graph such that each vertex is a part of at least one subtree. The bounded tree cover problem (BTC) requires to find a tree cover with minimum number of subtrees of bounded weight. This paper considers two generalized versions of BTC. The first problem deals with graphs having multiple weight functions. Two variations called strong and weak tree cover problems are defined. In strong tree cover, every subtree must be bounded with respect to all weight functions, whereas in weak tree cover, each subtree must be bounded with respect to at least one weight function. We consider only metric weight functions. A 4-approximation algorithm for strong tree cover and an \(O(\log n)\)-approximation algorithm for weak tree cover problem has been proposed. In the second problem, the objective is to find a tree cover where the bounds of the subtrees are not necessarily same. We show that this problem cannot be approximated within a constant factor unless P=NP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1), 1–18 (2006)
Even, G., Garg, N., Könemann, J., Ravi, R., Sinha, A.: Min-max tree covers of graphs. Oper. Res. Lett. 32(4), 309–315 (2004)
Frederickson, G.N., Matthew S. Hecht, Kim, C.E.: Approximation algorithms for some routing problems. In: 17th Annual Symposium on Foundations of Computer Science, pp. 216–227, October 1976
Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Gabow, H.N., Ronald, F. (eds). Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore May 22–24, pp. 396–402. ACM (2005)
Guttmann-Beck, N., Hassin, R.: Approximation algorithms for min-max tree partition. J. Algorithms 24(2), 266–286 (1997)
Khani, M.R., Salavatipour, M.R.: Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69(2), 443–460 (2014)
Nagamochi, H.: Approximating the minmax rooted-subtree cover problem. IEICE Trans. 88(5), 1335–1338 (2005)
Nagarajan, V., Ravi, R.: Approximation algorithms for distance constrained vehicle routing problems. Networks 59(2), 209–214 (2012)
Rocklin, M., Pinar, A.: On clustering on graphs with multiple edge types. Internet Math. 9(1), 82–112 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Gorain, B., Mandal, P.S., Mukhopadhyaya, K. (2016). Approximation Algorithms for Generalized Bounded Tree Cover. In: Kaykobad, M., Petreschi, R. (eds) WALCOM: Algorithms and Computation. WALCOM 2016. Lecture Notes in Computer Science(), vol 9627. Springer, Cham. https://doi.org/10.1007/978-3-319-30139-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-30139-6_21
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-30138-9
Online ISBN: 978-3-319-30139-6
eBook Packages: Computer ScienceComputer Science (R0)