An Experimental Study ofk-vertex Connectivity Algorithms

We present an algorithm for the k-vertex connectivity problem, which runs in O(km) time. The time complexity of the algorithm depends on the connectivity, k, and the edges number, m. The algorithm mainly performs Breadth first search (BFS) to findall the disjoint paths. The goal of this paper is to provide an experimental comparison of the efficiency of k-vertex algorithms. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. We study the state-of-artMax-Flow/Min-Cutalgorithms; ‘Dinic’, ‘Push-relabel’, and ‘Pseudoflow’. Experiments show that our algorithm performs well onk-vertex connectivity problem