报告人：侯建锋

报告时间：2021年4月8日10点

报告地点：大学科技园南815室

报告题目：On graph partitioning problems

侯建锋于2019年11月至2021年3月到华为香港研究所访学，本报告对访学期间所做的科研工作进行汇报，欢迎感兴趣的师生参加。

报告人简介：侯建锋，福州大学教授，博士生导师，福州大学“旗山学者”。2009年7月毕业于山东大学数学学院，获理学博士学位。2011年度全国优秀博士学位论文提名奖，2011年度福建省自然科学基金杰出青年项目获得者，2020年入选福建省“雏鹰计划”，主持国家自然科学基金4项，参与重点项目1项。主要从事图论及其应用研究，解决了图与超图划分领域的多个猜想和公开问题，发表论文50余篇。
 

报告摘要：Graph partitioning problems usually ask for
a partition of the vertex set of a graph into pairwise disjoint subsets with
various requirements. For instance, given a graph $G$, the well-known
(unweighted) Min-Cut problem (or Max-Cut problem) asks for a bipartition
$(V_1,V_2)$ of $G$ that minimizes (or maximizes) the number of crossing edges.
In practice, we may need to find a partition bounding not only the number of
crossing edges, but also the number of vertices in each part. This leads to the
ratio cut of graphs.

In this talk, I will give some results on Max-Cut and ratio cut of graphs.