An Experimental Study ofk-vertex Connectivity Algorithms
Main Article Content
Abstract
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.
Article Details
How to Cite
Rigat, A. (2012). An Experimental Study ofk-vertex Connectivity Algorithms. INFOCOMP Journal of Computer Science, 11(2), 1–9. Retrieved from https://infocomp.dcc.ufla.br/index.php/infocomp/article/view/351
Section
Articles
Upon receipt of accepted manuscripts, authors will be invited to complete a copyright license to publish the paper. At least the corresponding author must send the copyright form signed for publication. It is a condition of publication that authors grant an exclusive licence to the the INFOCOMP Journal of Computer Science. This ensures that requests from third parties to reproduce articles are handled efficiently and consistently and will also allow the article to be as widely disseminated as possible. In assigning the copyright license, authors may use their own material in other publications and ensure that the INFOCOMP Journal of Computer Science is acknowledged as the original publication place.