The acyclic orientation game on random graphs

Noga Alon, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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
Volume6
Issue number2-3
DOIs
StatePublished - 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

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

Cite this