A new distributed depth-first-search algorithm
type: Item
instance of: scholarly article
title: A new distributed depth-first-search algorithm
zbMATH Open document ID: 0573.68013
DOI: 10.1016/0020-0190(85)90083-3
author: Baruch Awerbuch
published in: Information Processing Letters
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3915620
zbMATH Keywords: distributed system
zbMATH Keywords: communication graph
zbMATH Keywords: time complexity
zbMATH Keywords: communication complexity
zbMATH Keywords: asynchronous communication network
MaRDI profile type: Publication
full work available at URL: 0020-0190(85)90083-3
OpenAlex ID: W1990389251
cites work: Graph Traversal Techniques and the Maximum Flow Problem in Distributed Computation
cites work: Parallel Computations in Graph Theory
cites work: Q4195963
cites work: Q3883524
description: scientific article; zbMATH DE number 3915620