It is shown that in the random graph Gnp with (fixed) edge probability p > 0, the number of edges that have to be examined in order to identify an acyclic orientation is θ(n log n) almost surely. For unrestricted p, an upper bound of O(n log3n) is established. Graphs G = V, E in which all edges have to be examined are considered, as well.
|Original language||English (US)|
|Number of pages||8|
|Journal||Random Structures & Algorithms|
|State||Published - 1995|
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics