2019/10/06 by Yong Chen, Zhi‐Zhong Chen, Chen, Yong +7
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1910.02470
Given a simple connected graph G = (V, E), we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as \em min-max balanced connected graph partition into k parts and denote it as \sc k-BGP. The general vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm; the vertex-weighted \sc 2-BGP and \sc 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively; but no approximability result exists for \sc k-BGP when k ≥ 4, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality \sc 3-BGP and then extend it to become a k/2-approximation for \sc k-BGP, for any constant k ≥ 3. Furthermore, for \sc 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could be useful for related graph partition problems.