Distributed Algorithms for SCC Decomposition

• Název česky: Distribuované algoritmy pro dekompozici na silně souvislé komponenty
• Autoři: BARNAT Jiří; CHALOUPKA Jakub; VAN DE POL Jaco
• Rok publikování: 2011
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Journal of Logic and Computation
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: http://logcom.oxfordjournals.org/content/early/2009/02/17/logcom.exp003
• Doi: http://dx.doi.org/10.1093/logcom/exp003
• Obor: Informatika
• Klíčová slova: parallel algorithms; strongly connected components
• Popis: Článek analyzuje existující paralelní algoritmy pro dekompozici grafu na silně souvislé komponenty s cílem identifikovat jednotlivé procedury, ze který se tyto paralelní algoritmy skládají. Dále článek ukazuje, jak vyskládat z identifikovaných primitiv nový algoritmus pro řešení daného problému, tzv. algoritmus Rekurzivní OBF. V práci dále demonstrujeme na důkladné experimentální studii, že nový algoritmus je výkonější než dosud známé algoritmy.

Související projekty

• Techniky automatické verifikace a validace softwarových a hardwarových systémů
• Vysoce paralelní a distribuované výpočetní systémy
• Verifikace a analýza velmi velkých počítačových systémů