Geodesic
Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 4, pp. 811-846.

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

In this paper we consider a natural generalization of the well-known MAX LEAF SPANNING TREE problem. In the generalized WEIGHTED MAX LEAF problem we get as input an undirected connected graph G, a rational number k not smaller than 1 and a weight function w: V → Q ≥ 1 on the vertices, and are asked whether a spanning tree T for G exists such that the combined weight of the leaves of T is at least k. We show that it is possible to transform an instance 〈G,w,k 〉 of WEIGHTED MAX LEAF in polynomial time into an equivalent instance 〈G′,w′,k′〉 such that |V(G′)| ≤ 5.5k and k′ ≤ k. In the context of parameterized complexity this means that WEIGHTED MAX LEAF admits a kernel with 5.5k vertices. The analysis of the kernel size is based on a new extremal result which shows that every graph G = (V,E) that excludes some simple substructures always contains a spanning tree with at least |V|/5.5 leaves. We also prove that WEIGHTED MAX LEAF does not admit a polynomial-time factor O(n1/2 − ε) or O( OPT1/3 − ε) approximation algorithm for any ε > 0 unless P=NP.
DOI : 10.7155/jgaa.00279
Keywords: max leaf, spanning tree, kernelization, weighted problem 
@article{JGAA_2012_16_4_a1,
     author = {Bart Jansen},
     title = {Kernelization for {Maximum} {Leaf} {Spanning} {Tree} with {Positive} {Vertex} {Weights}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {811--846},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2012},
     doi = {10.7155/jgaa.00279},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00279/}
}
TY  - JOUR
AU  - Bart Jansen
TI  - Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 811
EP  - 846
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00279/
DO  - 10.7155/jgaa.00279
LA  - en
ID  - JGAA_2012_16_4_a1
ER  - 
%0 Journal Article
%A Bart Jansen
%T Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
%J Journal of Graph Algorithms and Applications
%D 2012
%P 811-846
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00279/
%R 10.7155/jgaa.00279
%G en
%F JGAA_2012_16_4_a1
Bart Jansen. Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 4, pp. 811-846. doi : 10.7155/jgaa.00279. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00279/

Cité par Sources :