Generalized Bounded Tree Cover of a Graph - Gorain, Barun; Mandal, Partha Sarathi; Mukhopadhyaya, Krishnendu (Journal of Graph Algorithms and Applications, 2017)
A tree cover of a graph is a collection of subgraphs such that each vertex is a part of at least one subgraph and each subgraph is a tree.The bounded tree cover problem (BTC) finds a tree cover with minimum number of trees of bounded weight.This paper considers several generalized versions of BTC. The first problem deals with graphs having multiplemetric weight functions. Strong and weak tree cover problems are two variations of the first problem.In strong tree cover, every tree must be bounded with respect to all weight functions,whereas in weak tree cover, each tree must be bounded with respect to at least one weight function.A 4-approximation algorithm for strong tree cover and an $O(\log n)$-approximation algorithm for weak treecover problem are proposed. The objective of the second problem is to find a tree cover where bounds of thetrees in the tree cover are not necessarily same. It is proved that this problem cannot be approximated within a constantfactor unless P=NP. A constant factor approximation algorithm is proposed when the ratio of maximum andminimum bounds is bounded by a constant. The third problem considers BTC for a graph with a generalweight function which is not necessarily metric. A 3-approximation algorithm is proposed for this problem.