Efficient distributed breadth-first search algorithm

Makki S.A.M. (1996) Efficient distributed breadth-first search algorithm. Computer Communications, 19 8: 628-636. doi:10.1016/S0140-3664(96)01094-8


Author Makki S.A.M.
Title Efficient distributed breadth-first search algorithm
Journal name Computer Communications   Check publisher's open access policy
ISSN 0140-3664
Publication date 1996-01-01
Sub-type Article (original research)
DOI 10.1016/S0140-3664(96)01094-8
Volume 19
Issue 8
Start page 628
End page 636
Total pages 9
Language eng
Subject 1705 Computer Networks and Communications
2208 Electrical and Electronic Engineering
Abstract We present a more efficient Distributed Breadth-First Search algorithm for an asynchronous communication network. In the best case, the algorithm only uses 2(|V| - 1) messages and 2|l| units of time, where |V| is the number of sites in the network and |l| is the maximum level assigned to any node. In the worst case, the algorithm also has better complexity than previous algorithms. The improvement over previous algorithms is achieved by more sophisticated synchronization.
Keyword Breadth-First Search
Distributed systems
Parallel computing
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 3 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 12 Jul 2016, 10:59:16 EST by System User