Speaker：Jianfeng Hou, Center for Discrete Mathematics, Fuzhou University
When：Wednesday, 2020, June 17，3：00-4：00
Abstract：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 (V1, V2) 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.