Name
Title | ||
|---|---|---|
Implementation an Experimental Evaluation of Graph Connectivity Algorithms Using LEDA |
Abstract | ||
|---|---|---|
In this paper we describe robust and efficient implementations of two graph connectivity algorithms. The implementations are based on the LEDA library of efficient data types and algorithms [18,19]. Moreover, we provide experimental evaluations of the implemented algorithms and we compare their performance to other graph connectivity algorithms currently implemented in LEDA. The first algorithm is the Karp and Tarjan algorithm [16] for finding the connected components of an undirected graph. The algorithm achieves to find the connected components of a graph G = -V,E} in O(|V|) expected time. This is the first expected-time algorithm for the static graph connectivity problem implemented in LEDA. The experimental evaluation of the algorithm proves that the algorithm performs well in practice, and establishes that theoretical and experimental results converge. The standard procedure provided by LEDA for finding the connected components of a graph, called COMPONENTS has running time O(|V|+|E|). We have compared the performance of Karp and Tarjan's algorithm to the one of COMPONENTS and we have proved that there exists a wide class of graphs (those that they are dense) that the performance of the first algorithm dramatically improves upon the one of the second. The second implemented algorithm is the Nikoletseas, Reif, Spirakis and Yung polylogarithmic algorithm [20] for dynamic graph connectivity. The algorithm can cope with any random sequence of three kinds of operations: insertions, deletions and queries. The experimental evaluation of the algorithm proves that it is very efficient for particular classes of graphs. Comparing the performance of the implemented algorithm to the one of other dynamic connectivity algorithms implemented in LEDA, we conclude that the algorithm always performs better than all these algorithms for dense random graphs and random sequences of operations. Moreover, it works very efficiently even for sparse random graphs when the sequence of operations is long. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/3-540-48318-7_12 | Algorithm Engineering |
Keywords | Field | DocType |
tarjan algorithm,graph connectivity,experimental evaluation,yung polylogarithmic algorithm,graph connectivity algorithm,graph g,connected component,dense random graph,expected-time algorithm,dynamic graph connectivity,random sequence,data type | Modular decomposition,Line graph,Computer science,Algorithm,Theoretical computer science,Hopcroft–Karp algorithm,Suurballe's algorithm,Tarjan's strongly connected components algorithm,Connectivity,Reverse-delete algorithm,Graph (abstract data type),Distributed computing | Conference |
Volume | ISSN | ISBN |
1668 | 0302-9743 | 3-540-66427-0 |
Citations | PageRank | References |
1 | 0.35 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiota Fatourou | 1 | 281 | 28.16 |
| Paul G. Spirakis | 2 | 2222 | 299.05 |
| Panagiotis Zarafidis | 3 | 7 | 1.09 |
| Anna Zoura | 4 | 1 | 0.69 |