An Extended Experimental Evaluation of SCC (Gabows vs Kosarajus) based on Adjacency List
Keywords:
graph algorithms, directed graph, SCC (strongly connected components), transitive closure
Abstract
We present the results of a study comparing three strongly connected components algorithms. The goal of this work is to extend the understandings and to help practitioners choose appropriate options. During experiment, we compared and analysed strongly connected components algorithm by using dynamic graph representation (adjacency list). Mainly we focused on i. Experimental Comparison of strongly connected components algorithms. ii. Experimental Analysis of a particular algorithm. Our experiments consist large set of random directed graph with N number of vertices V and edges E to compute graph performance using dynamic graph representation. We implemented strongly connected graph algorithms, tested and optimized using efficient data structure. The article presents detailed results based on significant performance, preferences between SCC algorithms and provides practical recommendations on their use. During experimentation, we found some interesting results particularly efficiency of Cheriyan-Mehlhorn-Gabow's as it is more efficient in computing strongly connected components then Kosaraju's algorithm
Downloads
- Article PDF
- TEI XML Kaleidoscope (download in zip)* (Beta by AI)
- Lens* NISO JATS XML (Beta by AI)
- HTML Kaleidoscope* (Beta by AI)
- DBK XML Kaleidoscope (download in zip)* (Beta by AI)
- LaTeX pdf Kaleidoscope* (Beta by AI)
- EPUB Kaleidoscope* (Beta by AI)
- MD Kaleidoscope* (Beta by AI)
- FO Kaleidoscope* (Beta by AI)
- BIB Kaleidoscope* (Beta by AI)
- LaTeX Kaleidoscope* (Beta by AI)
How to Cite
Published
2013-08-15
Issue
Section
License
Copyright (c) 2013 Authors and Global Journals Private Limited
This work is licensed under a Creative Commons Attribution 4.0 International License.