J 2011

Distributed Algorithms for SCC Decomposition

BARNAT, Jiří, Jakub CHALOUPKA and Jaco VAN DE POL

Basic information

Original name

Distributed Algorithms for SCC Decomposition

Name in Czech

Distribuované algoritmy pro dekompozici na silně souvislé komponenty

Authors

BARNAT, Jiří (203 Czech Republic, guarantor, belonging to the institution), Jakub CHALOUPKA (203 Czech Republic, belonging to the institution) and Jaco VAN DE POL (528 Netherlands)

Edition

Journal of Logic and Computation, Oxford University Press, 2011, 0955-792X

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United Kingdom of Great Britain and Northern Ireland

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

Impact factor

Impact factor: 0.611

RIV identification code

RIV/00216224:14330/11:00049494

Organization unit

Faculty of Informatics

DOI

UT WoS

000286911500003

Keywords (in Czech)

paralelní algoritmy; silně souvislé komponenty

Keywords in English

parallel algorithms; strongly connected components

Tags

International impact, Reviewed
Změněno: 20/12/2011 14:41, prof. RNDr. Jiří Barnat, Ph.D.

Abstract

ORIG CZ

V originále

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.

In Czech

Článek analyzuje existující paralelní algoritmy pro dekompozici grafu na silně souvislé komponenty s cílem identifikovat jednotlivé procedury, ze který se tyto paralelní algoritmy skládají. Dále článek ukazuje, jak vyskládat z identifikovaných primitiv nový algoritmus pro řešení daného problému, tzv. algoritmus Rekurzivní OBF. V práci dále demonstrujeme na důkladné experimentální studii, že nový algoritmus je výkonější než dosud známé algoritmy.

Links

GA201/09/1389, research and development project
Name: Verifikace a analýza velmi velkých počítačových systémů
Investor: Czech Science Foundation, Verification and Analysis of Large-Scale Computer Systems
MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1ET408050503, research and development project
Name: Techniky automatické verifikace a validace softwarových a hardwarových systémů
Investor: Academy of Sciences of the Czech Republic, Techniques for automatic verification and validation of software nad hardware systems