Open Access Issue
Approximation Algorithms for Graph Partition into Bounded Independent Sets
Tsinghua Science and Technology 2023, 28 (6): 1063-1071
Published: 28 July 2023
Abstract PDF (5.5 MB) Collect

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.

Total 1