zbMATH — the first resource for mathematics

A new distributed depth-first-search algorithm. (English) Zbl 0573.68013
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 T.-Y. Cheung [IEEE Trans. Software Eng. SE-9, 504-512 (1983; Zbl 0513.68066)], requires O(\(| E|)\) both in communication and time complexities.

68Q25 Analysis of algorithms and problem complexity
68N25 Theory of operating systems
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Cheung, T., Graph traversal techniques and the maximum flow problem in distributed computation, IEEE trans. software engineering, SE-9, 4, 504-512, (1983) · Zbl 0513.68066
[2] Chang, E.J.H., Echo algorithms: depth parallel operations on general graphs, IEEE trans. software engineering, SE-8, 4, 391-401, (1982)
[3] Arjomandi, E.R.; Corneil, D., Parallel computations in graph theory, SIAM J. comput., 7, (1978)
[4] Eckshtein, D.; Alton, D., Parallel graph processing using depth-first search, ()
[5] Even, S., Graph algorithms, (1979), Computer Science Press Potomac, MD · Zbl 0441.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.