.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithms for Graph Partition into Bounded Independent Sets
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2022.9010062.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 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.
Keywords:
Color
Approximation algorithms
Partitioning algorithms
Bipartite graph
Computational complexity
graph partition
independent set
2-colorable graph
approximation algorithm
Journal
T
IF:
3.5
Papers:
987
Citations:
2.5K