Geodesic
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021 , Tome 26 (2022) no. 2, pp. 209-224.

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

Given a connected vertex-weighted graph $G$, the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of $G$ that maximizes the total weight of internal nodes. This problem is NP-hard and APX-hard, with the currently best known approximation factor $1/2$ (Chen et al., Algorithmica 2019). For the case of claw-free graphs, Chen et al. present an involved approximation algorithm with approximation factor $7/12$. They asked whether it is possible to improve these ratios, in particular for claw-free graphs and cubic graphs. For cubic graphs we present an algorithm that computes a spanning tree whose total weight of internal vertices is at least $\frac{3}{4}-\frac{3}{n}$ times the total weight of all vertices, where $n$ is the number of vertices of $G$. This ratio is almost tight for large values of $n$. For claw-free graphs of degree at least three, we present an algorithm that computes a spanning tree whose total internal weight is at least $\frac{3}{5}-\frac{1}{n}$ times the total vertex weight. The degree constraint is necessary as this ratio may not be achievable if we allow vertices of degree less than three. With the above ratios, we immediately obtain better approximation algorithms with factors $\frac{3}{4}-\epsilon$ and $\frac{3}{5}-\epsilon$ for the MaxwIST problem in cubic graphs and claw-free graphs having no degree-2 vertices, for any $\epsilon>0$. The new algorithms are short (compared to that of Chen et al.) and fairly simple as they employ a variant of the depth-first search algorithm. Moreover, they take linear time while previous algorithms for similar problem instances are super-linear.
DOI : 10.7155/jgaa.00590
Keywords: approximation algorithms, vertex-weighted trees, internal spanning trees, cubic graphs, claw-free graphs, depth-first search 
@article{JGAA_2022_26_2_a1,
     author = {Ahmad Biniaz},
     title = {Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {209--224},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2022},
     doi = {10.7155/jgaa.00590},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00590/}
}
TY  - JOUR
AU  - Ahmad Biniaz
TI  - Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 209
EP  - 224
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00590/
DO  - 10.7155/jgaa.00590
LA  - en
ID  - JGAA_2022_26_2_a1
ER  - 
%0 Journal Article
%A Ahmad Biniaz
%T Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
%J Journal of Graph Algorithms and Applications
%D 2022
%P 209-224
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00590/
%R 10.7155/jgaa.00590
%G en
%F JGAA_2022_26_2_a1
Ahmad Biniaz. Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 15th International Conference and  Workshops on Algorithms and Computation, WALCOM 2021
					, Tome 26 (2022) no. 2, pp. 209-224. doi : 10.7155/jgaa.00590. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00590/

Cité par Sources :