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
• 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