Algorithms for 2-Balanced Connected k-Partition Problem in Graphs
摘要
Motivated by the task of partitioning a tree into edge-disjoint subtrees of approximately equal size, we study the 2-balanced connected graph vertex k-partition problem. In this paper, utilizing the “charity vertex” method, we improve the results obtained by Caragiannis et al., demonstrating that the lower bound of the 2-balanced connected graph vertex k-partition problem is tight for connected graphs with a finite number of vertices that satisfy the charity vertices set size constraint.