We present an algorithm for testing the k-vertex-connectivity of graphs with given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. A graph G with n vertices and maximum degree at most d is calledε-far from k-vertex-connectivity when at least εdn/2 edges must be added to or removed from G to obtain a k-vertex-connected graph with maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is ε-far from k-vertex-connectivity with a probability of at least 2/3. The algorithm runs in O(d(c/εd){sup}k log 1/εd) time (c>1 is a constant) for given (k-1)-vertex-connected graphs, and O(d(ck/εd){sup}k log k/εd ) time (c>1 is a constant) for given general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4.
展开▼
机译：我们介绍了一种用于测试具有给定最大程度的k-顶点连接的算法。算法的时间复杂性与图形的顶点和边缘的数量无关。当必须将至少εdn/ 2边缘加入或从g中移除时，具有n顶点和最多d最多d的图形g远离k - 顶点连接，以获得最大程度的k角连接图大多数d。该算法总是接受每个k角连接的图表，并拒绝ε-远离k角连接的图表，概率至少为2/3。该算法在O（d（c /εd）{sup} k log 1 /εd）中运行（c> 1是常数）给定（k-1） - 连接图和o（d（ck /对于给定的一般图，εd）{sup} k log k /εd）时间（c> 1是常数）。它是一般k≥4的第一恒定时间k角连接测试算法。
展开▼
