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.
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