Parallel Algorithms for Finding SCCs in Implicitly Given Graphs
BARNAT, Jiří and Pavel MORAVEC. Parallel Algorithms for Finding SCCs in Implicitly Given Graphs. In Formal Methods: Applications and Technology. Berlin, Heidelberg: Springer-Verlag, 2007, p. 316-330. ISBN 978-3-540-70951-0. |
Other formats:
BibTeX
LaTeX
RIS
|
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ří (203 Czech Republic, guarantor) and Pavel MORAVEC (203 Czech Republic). |
Edition | Berlin, Heidelberg, Formal Methods: Applications and Technology, p. 316-330, 15 pp. 2007. |
Publisher | Springer-Verlag |
Other information | |
---|---|
Original language | English |
Type of outcome | Proceedings paper |
Field of Study | 10201 Computer sciences, information science, bioinformatics |
Country of publisher | Germany |
Confidentiality degree | is not subject to a state or trade secret |
RIV identification code | RIV/00216224:14330/07:00019374 |
Organization unit | Faculty of Informatics |
ISBN | 978-3-540-70951-0 |
UT WoS | 000245773800022 |
Keywords in English | distributed verification; SCCs |
Tags | distributed verification, SCCS |
Tags | International impact, Reviewed |
Changed by | Changed by: prof. RNDr. Jiří Barnat, Ph.D., učo 3496. Changed: 23/6/2009 10:21. |
Abstract |
---|
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. |
Abstract (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 |
PrintDisplayed: 27/9/2024 19:55