文献类型：期刊文献

英文题名：An Improved Approximation Algorithm fortheMinimum k-Star Partition Problem

作者：Xu, Tong[1]; Yu, Wei[1]; Liu, Zhaohui[1]

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2026

卷号：15983 LNCS

起止页码：81

外文期刊名：Lecture Notes in Computer Science

收录：EI(收录号：20253419003690)

语种：英文

外文关键词：Computation theory - Graph algorithms - Local search (optimization) - Stars - Undirected graphs

摘要：Given an undirected graph G=(V,E), the minimum k-star partition problem is to find a collection of vertex-disjointstars 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 achievesan approximation ratio of k2-k-2k(k+1) when k≥5 is even and k2-k-22k2 when k≥5 is odd. This improves on the previous best k2-approximation algorithm implied by Hell and Kirkpatrick for each k≥5.In addition, we give examples to show that our analysis is tight. ? The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.