Parallel Algorithms for Finding SCCs in Implicitly Given Graphs

BARNAT, Jiří and 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, p. 20-34.

Basic information

Original name

Parallel Algorithms for Finding SCCs in Implicitly Given Graphs

Name in Czech

Paralelní algoritmy pro hledání silně souvislých komponent v implicitně zadaných grafech

Authors

BARNAT, Jiří and Pavel MORAVEC

Edition

Bonn, Germany, Proceedings of the 5th International Workshop on Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2006), p. 20-34, 2006

Publisher

University Bonn

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Organization unit

Faculty of Informatics

UT WoS

000245773800022

Keywords in English

distributed verification; SCCs

Tags

distributed verification, SCCS

Tags

International impact, Reviewed

---

Abstract

V originále

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.

In Czech

Č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.

---

Links

GA201/06/1338, research and development project	Name: Automatizovaná verifikace softwaru Investor: Czech Science Foundation, Automated software verification
GD102/05/H050, research and development project	Name: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů Investor: Czech Science Foundation, Integrated approach to education of PhD students in the area of parallel and distributed systems
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1ET408050503, research and development project	Name: Techniky automatické verifikace a validace softwarových a hardwarových systémů Investor: Academy of Sciences of the Czech Republic, Techniques for automatic verification and validation of software nad hardware systems
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science