Vertex bisection is a graph partitioning problem in which the aim is to find a partition into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. We are interested in giving upper bounds on the vertex bisection width of random $d$-regular graphs for constant values of $d$. Our approach is based on analyzing a greedy algorithm by using the Differential Equations Method. In this way, we obtain the first known upper bounds for the vertex bisection width in random regular graphs. The results are compared with experimental ones and with lower bounds obtained by Kolesnik and Wormald, (Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs, SIAM J. on Disc. Math. 28(1), 553-575, 2014).
翻译：vertex 分形是一个图形分割问题, 其目的在于找到一个分隔点, 将一个分隔点中的脊椎数量减少到两个相等的部位, 从而最小化于另一个分隔点中有一个相邻的分块。 我们有兴趣在随机的 $d$- 普通图形的顶端部分宽度上给定值为 $d$ 的常数。 我们的方法是基于使用差异方位法分析贪婪的算法。 这样, 我们就可以在随机的普通图形中获取第一个已知的顶端括号宽的上限。 其结果与实验值和Kolesnik 和 Wormald 获得的下限进行了比较( 随机正态图形的等谱数的下边框, SIAM J. on Disc. Math. 28(1), 553-575, 2014)。
相关内容
微信扫码咨询专知VIP会员