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 al...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.展开更多
基金partially supported by the Fundamental Research Funds for the Central Universities,Nankai Universitypartially supported by NSFC(Nos.12161141006,12111540249)+2 种基金the Natural Science Foundation of Tianjin(No.20JCJQJC00090)the Fundamental Research Funds for the Central Universities,Nankai Universitypartially supported by grant DFF-7014-00037B of Independent Research Fund Denmark。
基金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)。
文摘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.
