BARNAT, Jiří a Pavel MORAVEC. Parallel Algorithms for Finding SCCs in Implicitly Given Graphs. In Proceedings of the 5th International Workshop on Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2006). Bonn, Germany: University Bonn. s. 20-34. 2006.
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ří a Pavel MORAVEC.
Vydání Bonn, Germany, Proceedings of the 5th International Workshop on Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2006), s. 20-34, 2006.
Nakladatel University Bonn
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í
Organizační jednotka Fakulta informatiky
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: 6. 12. 2006 11:35.
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 VaVNázev: Automatizovaná verifikace softwaru
Investor: Grantová agentura ČR, Automatizovaná verifikace softwaru
GD102/05/H050, projekt VaVNá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ěrNá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 VaVNá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 VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky
VytisknoutZobrazeno: 29. 3. 2024 00:07