Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016)
DOI: 10.7155/jgaa.00416
Generalized Bounded Tree Cover of a Graph
Vol. 21, no. 3, pp. 265-280, 2017. Regular paper.
Abstract 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 multiple
metric 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 tree
cover problem are proposed. The objective of the second problem is to find a tree cover where bounds of the
trees in the tree cover are not necessarily same. It is proved that this problem cannot be approximated within a constant
factor unless P=NP. A constant factor approximation algorithm is proposed when the ratio of maximum and
minimum bounds is bounded by a constant. The third problem considers BTC for a graph with a general
weight function which is not necessarily metric. A 3-approximation algorithm is proposed for this problem.
|
Submitted: May 2016.
Reviewed: November 2016.
Revised: December 2016.
Accepted: December 2016.
Final: January 2017.
Published: February 2017.
|
Journal Supporters
|