The acyclic orientation game on random graphs

Noga Alon, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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 languageEnglish (US)
Pages (from-to)261-268
Number of pages8
JournalRandom Structures & Algorithms
Issue number2-3
StatePublished - 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'The acyclic orientation game on random graphs'. Together they form a unique fingerprint.

Cite this