实事求是 经世致用

宁波大学logo

甬江数学讲坛(2019年第7讲)

2019-05-20

报告题目:Approximation  algorithms for graph partition into balanced connected subgraphs

报  告 人:Guohui Lin(林国辉)  

  University of Alberta, Canada(加拿大阿尔伯特大学)  教授


报告时间:
20190423(星期二)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.