Skip to content Skip to navigation

Academic Events

On graph partitioning problems

SpeakerJianfeng Hou, Center for Discrete Mathematics, Fuzhou University

WhenWednesday, 2020, June 17300-400


AbstractGraph 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.