A new distributed depth-first-search algorithm (Q1062756): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Graph Traversal Techniques and the Maximum Flow Problem in Distributed Computation / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Parallel Computations in Graph Theory / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4195963 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3883524 / rank | |||
Normal rank | |||
Latest revision as of 18:48, 14 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new distributed depth-first-search algorithm |
scientific article |
Statements
A new distributed depth-first-search algorithm (English)
0 references
1985
0 references
This paper presents a new distributed Depth-First-Search (DFS) algorithm for an asynchronous communication network, whose communication and time complexities are O(\(| E|)\) and O(\(| V|)\), respectively. The output of the algorithm is the DFS tree, kept in a distributed fashion. The existing algorithm, due to \textit{T.-Y. Cheung} [IEEE Trans. Software Eng. SE-9, 504-512 (1983; Zbl 0513.68066)], requires O(\(| E|)\) both in communication and time complexities.
0 references
distributed system
0 references
communication graph
0 references
time complexity
0 references
communication complexity
0 references
asynchronous communication network
0 references
