Geodesic
Generalized Bounded Tree Cover of a Graph
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016) , Tome 21 (2017) no. 3, pp. 265-280.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00416
Keywords: Tree Cover, TSP, K-MST, Approximation Algorithms 
@article{JGAA_2017_21_3_a2,
     author = {Barun Gorain and Partha Sarathi Mandal and Krishnendu Mukhopadhyaya},
     title = {Generalized {Bounded} {Tree} {Cover} of a {Graph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {265--280},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2017},
     doi = {10.7155/jgaa.00416},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00416/}
}
TY  - JOUR
AU  - Barun Gorain
AU  - Partha Sarathi Mandal
AU  - Krishnendu Mukhopadhyaya
TI  - Generalized Bounded Tree Cover of a Graph
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 265
EP  - 280
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00416/
DO  - 10.7155/jgaa.00416
LA  - en
ID  - JGAA_2017_21_3_a2
ER  - 
%0 Journal Article
%A Barun Gorain
%A Partha Sarathi Mandal
%A Krishnendu Mukhopadhyaya
%T Generalized Bounded Tree Cover of a Graph
%J Journal of Graph Algorithms and Applications
%D 2017
%P 265-280
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00416/
%R 10.7155/jgaa.00416
%G en
%F JGAA_2017_21_3_a2
Barun Gorain; Partha Sarathi Mandal; Krishnendu Mukhopadhyaya. Generalized Bounded Tree Cover of a Graph. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation  (WALCOM 2016)
					, Tome 21 (2017) no. 3, pp. 265-280. doi : 10.7155/jgaa.00416. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00416/

Cité par Sources :