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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Algorithms for 2-Balanced Connected k-Partition Problem in Graphs

  • Jing Hu,
  • Junran Yu,
  • Xiaoyan Zhang

摘要

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.