Skip Navigation



Journal of Logic and Computation Advance Access published online on February 17, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp003
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Barnat, J.
Right arrow Articles by Van De Pol, J.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Distributed Algorithms for SCC Decomposition

Jirí Barnat and Jakub Chaloupka

Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic.
E-mail: barnat{at}fi.muni.cz; xchalou1{at}fi.muni.cz

Jaco Van De Pol

Formal Methods and Tools, Department of EEMCS, University of Twente, The Netherlands.
E-mail: j.c.vandepol{at}ewi.utwente.nl

Received 29 February 2008.


  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.

Keywords: parallel algorithms; strongly connected components


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.