Distributed algorithms for constructing a depth-first-search tree

Makki S.A.M. and Havas G. (1994). Distributed algorithms for constructing a depth-first-search tree. In: Proceedings of the 1994 International Conference on Parallel Processing, ICPP 1994. 23rd International Conference on Parallel Processing, ICPP 1994, Raleigh, NC, (). August 15, 1994-August 19, 1994. doi:10.1109/ICPP.1994.91


Author Makki S.A.M.
Havas G.
Title of paper Distributed algorithms for constructing a depth-first-search tree
Conference name 23rd International Conference on Parallel Processing, ICPP 1994
Conference location Raleigh, NC
Conference dates August 15, 1994-August 19, 1994
Proceedings title Proceedings of the 1994 International Conference on Parallel Processing, ICPP 1994   Check publisher's open access policy
Journal name Proceedings of the International Conference on Parallel Processing   Check publisher's open access policy
Series Proceedings of the International Conference on Parallel Processing
Publisher Institute of Electrical and Electronics Engineers Inc.
Publication Year 1994
Sub-type Fully published paper
DOI 10.1109/ICPP.1994.91
ISSN 0190-3918
Volume 3
Total pages 1
Abstract/Summary We present more efficient distributed depth-firstsearch algorithms which construct a depth-first-search tree for a communication network. The algorithms require left| V right|(1 + r) messages and |V|(l + r) units of time in the worst case, where left| V right| is the number of sites in the network, and 0 leqslant r le 1. The value of r depends on the network topology and possibly on the routing chosen. In the best case, when the underlying network has a ring topology, r = 0 and our basic algorithm requires V messages and time units, regardless of routing. We extend this algorithm to achieve the same best case bound for other topologies. The worst case bound, which has r = 1 - 2/left| V right|, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.
Subjects 1712 Software
2600 Mathematics
1708 Hardware and Architecture
Q-Index Code E1
Institutional Status Unknown

Document type: Conference Paper
Collection: Scopus Import - Archived
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 13 Sep 2016, 14:02:47 EST by System User