Parallel Algorithms for Finding SCCs in Implicitly Given Graphs
| BARNAT, Jiří a Pavel MORAVEC. Parallel Algorithms for Finding SCCs in Implicitly Given Graphs. In Formal Methods: Applications and Technology. Berlin, Heidelberg: Springer-Verlag, 2007, s. 316-330. ISBN 978-3-540-70951-0. |
|
Další formáty:
BibTeX
LaTeX
RIS
|
| Základní údaje | |
|---|---|
| Originální název | Parallel Algorithms for Finding SCCs in Implicitly Given Graphs |
| Název česky | Paralelní algoritmy pro hledání silně souvislých komponent v implicitně zadaných grafech |
| Autoři | BARNAT, Jiří (203 Česká republika, garant) a Pavel MORAVEC (203 Česká republika). |
| Vydání | Berlin, Heidelberg, Formal Methods: Applications and Technology, od s. 316-330, 15 s. 2007. |
| Nakladatel | Springer-Verlag |
| Další údaje | |
|---|---|
| Originální jazyk | angličtina |
| Typ výsledku | Stať ve sborníku |
| Obor | 10201 Computer sciences, information science, bioinformatics |
| Stát vydavatele | Německo |
| Utajení | není předmětem státního či obchodního tajemství |
| Kód RIV | RIV/00216224:14330/07:00019374 |
| Organizační jednotka | Fakulta informatiky |
| ISBN | 978-3-540-70951-0 |
| UT WoS | 000245773800022 |
| Klíčová slova anglicky | distributed verification; SCCs |
| Štítky | distributed verification, SCCS |
| Příznaky | Mezinárodní význam, Recenzováno |
| Změnil | Změnil: prof. RNDr. Jiří Barnat, Ph.D., učo 3496. Změněno: 23. 6. 2009 10:21. |
| Anotace |
|---|
| We examine existing parallel algorithms for detection of strongly connected components and discuss their applicability to the case when the graph to be decomposed is given implicitly. In particular, we list individual techniques that parallel algorithms for SCC detection are assembled from and show how to assemble a new more efficient algorithm for solving the problem. In the paper we also report on a preliminary experimental study we did to evaluate the new algorithm. |
| Anotace česky |
|---|
| Článek zkoumá existující algoritmy for detekci silně souvislých komponent a diskutuje jejich použitelnost v případě, že je vstupní graf zadán implicitně. Zejména jsou popsány techniky které tyto algoritmy používají. Je také prezentován nový efektivnější algoritmus využívající tyto techniky. V článku jsou také popsány předběžné výsledky experimentálního porovnání dřívějších algoritmů i nového. |
| Návaznosti | |
|---|---|
| GA201/06/1338, projekt VaV | Název: Automatizovaná verifikace softwaru |
| Investor: Grantová agentura ČR, Automatizovaná verifikace softwaru | |
| GD102/05/H050, projekt VaV | Název: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů |
| Investor: Grantová agentura ČR, Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaný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ů | |
| 1M0545, projekt VaV | Název: Institut Teoretické Informatiky |
| Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky | |
VytisknoutZobrazeno: 27. 4. 2024 04:12