J 2011

Distributed Algorithms for SCC Decomposition

BARNAT, Jiří; Jakub CHALOUPKA a Jaco VAN DE POL

Základní údaje

Originální název

Distributed Algorithms for SCC Decomposition

Název česky

Distribuované algoritmy pro dekompozici na silně souvislé komponenty

Autoři

BARNAT, Jiří; Jakub CHALOUPKA a Jaco VAN DE POL

Vydání

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

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Velká Británie a Severní Irsko

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.611

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/11:00049494

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

Klíčová slova česky

paralelní algoritmy; silně souvislé komponenty

Klíčová slova anglicky

parallel algorithms; strongly connected components

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 20. 12. 2011 14:41, prof. RNDr. Jiří Barnat, Ph.D.

Anotace

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.

Česky

Č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.

Návaznosti

GA201/09/1389, projekt VaV
Název: Verifikace a analýza velmi velkých počítačových systémů
Investor: Grantová agentura ČR, Verifikace a analýza velmi velkých počítačových systémů
MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1ET408050503, projekt VaV
Název: Techniky automatické verifikace a validace softwarových a hardwarových systémů
Investor: Akademie věd ČR, Techniky automatické verifikace a validace softwarových a hardwarových systémů