Approximation Algorithms for Graph Partition into Bounded Independent Sets

作     者：Jingwei Xie Yong Chen An Zhang Guangting Chen Jingwei Xie;Yong Chen;An Zhang;Guangting Chen

作者机构：Department of MathematicsHangzhou Dianzi UniversityHangzhou 310018China Zhejiang University of Water Resources and Electric PowerHangzhou 310018China 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2023年第28卷第6期

页      面：1063-1071页

核心收录：

学科分类：07[理学] 0701[理学-数学] 

基　　金：gment This work was supported by the National Natural Science Foundation of China(No.11971139) the Natural Science Foundation of Zhejiang Province(No.LY21A010014) the Fundamental Research Funds for the Provincial Universities of Zhejiang(No.GK22990929900)。 

主　　题：graph partition independent set 2-colorable graph approximation algorithm 

摘      要：The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.