科研工作
首页 科研工作 学术活动

信息与计算科学系侯建锋老师学术报告

信息来源: 暂无 发布日期: 2021-04-06 浏览次数:

 

报告人:侯建锋

报告时间:20214810

报告地点:大学科技园南815

报告题目:On graph partitioning problems

 

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

报告人简介:侯建锋,福州大学教授,博士生导师,福州大学旗山学者20097月毕业于山东大学数学学院,获理学博士学位。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.