| Identifikační kód | RIV/00216224:14330/11:00049494 |
|---|
| Název v anglickém jazyce | Distributed Algorithms for SCC Decomposition |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2011 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 3 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 2 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Jiří Barnat (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 5692792)
Jakub Chaloupka (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 5376327)
Jaco van de Pol (státní příslušnost: NL - Nizozemsko) |
|---|
| Popis výsledku v anglickém jazyce | 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. |
|---|
| Klíčová slova oddělená středníkem | parallel algorithms; strongly connected components |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1093/logcom/exp003 |
|---|