报告题目：Approximation algorithms for graph partition into balanced connected subgraphs
报告人： Guohui Lin(林国辉)
University of Alberta, Canada(加拿大阿尔伯特大学) 教授
报告时间：2019年04月23日(星期二)9:30-10:30
报告地点：龙赛理科楼北楼116
报告摘要： Given a simple connected graph G = (V, E) and a constant integer k >= 2, we seek to partition the vertex set V into k non-empty parts such that the subgraph induced on each part is connected, and the maximum-size of these parts is minimized. We refer this problem to as "graph partition into k balanced connected subgraphs" (k-BGP). The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. On general graphs, k-BGP is NP-hard for every constant k >= 2; from existing approximation results for a closely related edge-weighted variant, k-BGP can be approximated within k. In this paper, we present a 4/3-approximation for 2-BGP and a k/2-approximation algorithm for k-BGP, for any constant k >= 3. Furthermore, for 4-BGP, we propose an improved 15/8-approximation. To these purposes, we have designed several local improvement operations, which could be useful for related graph partition problems.
