Scholarlink

<p>Motivated by the result of balanced connected graph edge partition problem for trees, we investigate the 2-balanced connected graph vertex <i>k</i>-partition problem. This paper leverages the charity vertex method and proposes several algorithms for 2-balanced vertex-connected partitioning. Furthermore, we prove that these algorithms are polynomial-time solvable on degree-bounded graphs, thereby refining and extending the results of Caragiannis et al.</p>

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

Algorithms for 2-balanced connected k-partition problem in graphs

  • 期刊论文

  • 发表日期：

    2025年7月3日

查看全文
  • Junran Yu,
  • Jing Hu,
  • Jiaquan Gao,
  • Donglei Du,
  • Xiaoyan Zhang

摘要

Motivated by the result of balanced connected graph edge partition problem for trees, we investigate the 2-balanced connected graph vertex k-partition problem. This paper leverages the charity vertex method and proposes several algorithms for 2-balanced vertex-connected partitioning. Furthermore, we prove that these algorithms are polynomial-time solvable on degree-bounded graphs, thereby refining and extending the results of Caragiannis et al.