TY - JOUR
AU - Xie, Jingwei
AU - Chen, Yong
AU - Zhang, An
AU - Chen, Guangting
PY - 2023
TI - Approximation Algorithms for Graph Partition into Bounded Independent Sets
JO - Tsinghua Science and Technology
SN - 1007-0214
SP - 1063
EP - 1071
VL - 28
IS - 6
AB - 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 32-approximation algorithm for any 2-colorable graph is presented. An improved 75-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.
UR - https://doi.org/10.26599/TST.2022.9010062
DO - 10.26599/TST.2022.9010062