Distributed Algorithms for SCC Decomposition

Share/Save/Bookmark

Barnat, Jiri and Chaloupka, Jakub and Pol, Jaco van de (2009) Distributed Algorithms for SCC Decomposition. Journal of Logic and Computation, 21 (1). pp. 23-44. ISSN 0955-792X

open access
[img]
Preview
PDF (Author's version)
324kB
[img]
Preview
PDF (Publisher's version)
361kB
Abstract:We study existing parallel algorithms for the decomposition of a partitioned graph into its strongly connected components (SCCs). In particular, we identify several individual procedures that the algorithms are assembled from and show how to assemble a new and more efficient algorithm, called Recursive OBF (OBFR), to solve the decomposition problem. We also report on a thorough experimental study to evaluate the new algorithm. It shows that it is possible to perform SCC decomposition in parallel efficiently and that OBFR, if properly implemented, is the best choice in most cases.
Item Type:Article
Copyright:© 2009 Oxford University Press
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/67466
Official URL:http://dx.doi.org/10.1093/logcom/exp003
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 263759