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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom