Premium
The acyclic orientation game on random graphs
Author(s) -
Alon Noga,
Tuza Zsolt
Publication year - 1995
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.3240060213
Subject(s) - combinatorics , mathematics , directed acyclic graph , random graph , upper and lower bounds , orientation (vector space) , random regular graph , enhanced data rates for gsm evolution , graph , discrete mathematics , chordal graph , 1 planar graph , computer science , geometry , mathematical analysis , telecommunications
It is shown that in the random graph G n p 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 log 3 n) is established. Graphs G = (V, E) in which all edges have to be examined are considered, as well.