论文标题
关于随机$ d $ regular Graphs的顶点一分配宽度
On Vertex Bisection Width of Random $d$-Regular Graphs
论文作者
论文摘要
顶点分配是一个图形分区问题，其中的目的是将一个分区找到两个相等的部分，以最大程度地减少一个分区集中的顶点数量，而该分区集中的另一组中具有邻居。我们有兴趣在$ d $的常数值的随机$ d $ gromargular图表上给出上限。我们的方法基于使用微分方程方法分析贪婪算法。通过这种方式，我们在随机常规图中获得了顶点一分为二宽度的第一个已知上限。将结果与实验性的结果以及Kolesnik和Wormald获得的较低限制（均衡数量的随机常规图的下限，Siam J. onDisc。Math。28（1），553-575，553-575，2014）。
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).
