A 4/3-approximation algorithm for the Maximum Internal Spanning Tree Problem
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 131-140 |
| Journal / Publication | Journal of Computer and System Sciences |
| Volume | 118 |
| Online published | 12 Jan 2021 |
| Publication status | Published - Jun 2021 |
Link(s)
Abstract
In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G, the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4/3, which improves upon the best known performance ratio 3/2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4/3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard.
Research Area(s)
- Approximation algorithm, Maximum Internal Spanning Tree Problem, Performance ratio
Citation Format(s)
A 4/3-approximation algorithm for the Maximum Internal Spanning Tree Problem. / Li, Xingfu; Zhu, Daming; Wang, Lusheng.
In: Journal of Computer and System Sciences, Vol. 118, 06.2021, p. 131-140.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
