福建工程学院科研平台学术活动安排表
平台名称：福建工程学院应用数学研究所
| |||
时间 | 2019年10月16日14:30至15:30 | 地点 | 北区C4-314 |
主持人 | 林晶 | 联系电话 | 13950360890 |
主题 | 图的最大割和最大平衡划分 | ||
拟研讨的主要内容 |
Many classical partitioning problems in Combinatorics and Computer Science seek a partition of a combinatorial object which optimizes a single parameter. Two famous examples are Max Cut and Max Bisection. These problems are usually NP-hard. The Max-Cut problem is to partition the vertex set V into two disjoint parts V1 and V2 so that the number of edges of G crossing between V1 and V2 is maximal. The Max-Bisection problem has the additional constraint that the two vertex classes should differ in size by at most one. Alon et al. (2003) conjectured that, for any fixed graph H, there exists a c=c(H) > 0 such that the Max Cut f (m, H) >= m/2 + cm^{3/4}. We confirm the conjecture asymptotically for some H. Moreover, inspired by Alon's method, we also give a lower bound on max-bisections of graphs without short cycles.
| ||