A new distributed depth-first-search algorithm (Q1062756)
From MaRDI portal
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
