Recognizing unordered depth-first search trees of an undirected graph in parallel

Authors
Peng, CH Wang, BF Wang, JS
Citation
Ch. Peng et al., Recognizing unordered depth-first search trees of an undirected graph in parallel, IEEE PARALL, 11(6), 2000, pp. 559-570
Citations number
16
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN journal
10459219 → ACNP
Volume
11
Issue
6
Year of publication
2000
Pages
559 - 570
Database
ISI
SICI code
1045-9219(200006)11:6<559:RUDSTO>2.0.ZU;2-0
Abstract
Let G be an undirected graph and T be a spanning tree of G. In this paper, an efficient parallel algorithm is proposed for determining whether T is an unordered depth-first search tree of G. The proposed algorithm runs in O(m /p + log m) time using p processors on the EREW PRAM, where m is the number of edges contained in G. It is cost-optimal and achieves linear speedup.