.png){kind=icon}
.png){kind=icon}
Return
An Improved Approximation Algorithm for the Minimum k-Star Partition Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given an undirected graph G = (V, E), the minimum.k-star partition problem is to find a collection of vertex-disjoint stars containing at most.k vertices to cover all the vertices of.V. The objective is to minimize the number of stars in the collection. In this paper, we give a local search algorithm which achieves an approximation ratio of (k)/(2) -(k-2)/(k(k+1)) when k >= 5 is even and (k)/(2) - (k-2)/(2k)2 when k >= 5 is odd. This improves on the previous best (k)/(2) -approximation algorithm implied by Hell and Kirkpatrick for each k >= 5. In addition, we give examples to show that our analysis is tight.
Keywords:
Approximation Algorithm
Star Partition
Path Partition
Local Search
Journal
C
IF:
0
Papers:
24
Citations:
0