No label defined (Q3703296)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3930349
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3930349 |
Statements
1985
0 references
0.98900443
0 references
0.9767262
0 references
0 references
0 references
0.94397116
0 references
0.9436912
0 references
[For the entire collection see Zbl 0568.00020.] An algorithm is presented that computes connected components of a graph \(G=(V,E)\). As a model of computation the SIMD-SM (Single instruction stream, multiple data stream-shared memory) computer is used. The algorithm needs O(log\(| V|)\) time, \(O(| V| +| E|)\) space and \(0(| V| +| E|)\) processors in the case of the concurrent-read, concurrent-write model, or \(O(\log^ 2| V|)\) time, \(O(| V| +| E|)\) space and \(O((| V| +| E|)/\log | V|)\) processors both for the exclusive- read, exclusive-write model, and the concurrent-read, exclusive-write model.
0 references