Improved Distributed Algorithms for SCC Decomposition

• Název česky: Vylepšené algoritmy pro distribuovanou dekompozici grafu na silně souvislé komponenty
• Autoři: BARNAT Jiří; CHALOUPKA Jakub; VAN DE POL Jaco
• Rok publikování: 2008
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Electronic Notes in Theoretical Computer Science
• Fakulta / Pracoviště MU: Fakulta informatiky
• Obor: Informatika
• Klíčová slova: SCC decomposition; parallel; distributed; OBF
• Popis: Článek popisuje vylepšení techniky OBF, která se používá pro paralelní a distribuovanou detekci silně souvislých komponent v grafu. Je představena rekurzivní varianta OBF a několik možných způsobů implementace. Nové přístupy jsou vyhodnoceny jak nad syntetickými grafy, tak i nad grafy reálných systémů. Naměřené hodnoty jsou porovnány s ostatními přístupy pro paralelní dekompozici grafu na silně souvislé komponenty.

Související projekty

• 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