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ří; MORAVEC Pavel
• Rok publikování: 2006
• Druh: Článek ve sborníku
• Konference: Proceedings of the 5th International Workshop on Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2006)
• Fakulta / Pracoviště MU: Fakulta informatiky
• Citace: 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, 2006, s. 20-34.
• Obor: Informatika
• Klíčová slova: distributed verification; SCCs
• Popis: Č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.

Související projekty

• Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů
• Techniky automatické verifikace a validace softwarových a hardwarových systémů
• Institut Teoretické Informatiky
• Vysoce paralelní a distribuované výpočetní systémy
• Automatizovaná verifikace softwaru