Can I read Better Approximation Algorithms for Maximum Weight Internal Spanning Trees in Cubic Graphs and Claw-free Graphs on EtoBox?

Better Approximation Algorithms for Maximum Weight Internal Spanning Trees in Cubic Graphs and Claw-free Graphs by Biniaz, Ahmad is a scholarly article available to read on EtoBox.

What is Better Approximation Algorithms for Maximum Weight Internal Spanning Trees in Cubic Graphs and Claw-free Graphs about?

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. We improve the approximation factors for the MaxwIST problem in cubic graphs and claw-free 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 achie

Author

Biniaz, Ahmad

Published

2020

Language

EN