Parallel Algorithms for Finding SCCs in Implicitly Given Graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00019374" target="_blank" >RIV/00216224:14330/07:00019374 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Parallel Algorithms for Finding SCCs in Implicitly Given Graphs
Original language description
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 algorithmsfor 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.
Czech name
Paralelní algoritmy pro hledání silně souvislých komponent v implicitně zadaných grafech
Czech description
Č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.

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)