RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Infocomp >

Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/9871

Title: An experimental study of k-vertex connectivity algorithms
???metadata.dc.creator???: Rigat, Azzeddine
Keywords: Graph algorithms
K-vertex connectivity
Maximum flow
Minimum cut
Network design problem
Algoritmos de grafos
Conectividade de vértices k
Fluxo máximo
Corte mínimo
Problema de design de rede
Publisher: Editora da UFLA
???metadata.dc.date???: 1-Jun-2012
Citation: RIGAT, A. An experimental study of k-vertex connectivity algorithms. INFOCOMP: Journal of Computer Science, Lavras, v. 11, n. 2, p. 1-9, June 2012.
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.
Other Identifiers: http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/351
???metadata.dc.language???: eng
Appears in Collections:Infocomp

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

View Statistics


DSpace Software Copyright © 2002-2010  Duraspace - Feedback