Premium
Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph
Author(s) -
Dyer Martin,
Friezet Alan
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020207
Subject(s) - parallelizable manifold , lexicographical order , depth first search , combinatorics , mathematics , graph , tree (set theory) , search tree , random graph , algorithm , computer science , discrete mathematics , search algorithm
We describe an O ((log n) 2 ) time parallel algorithm, using n processors, for finding the lexicographically first depth first search tree in the random graph G n, p , with p fixed. The problem itself is complete for P , and so is unlikely to be efficiently parallelizable always.