The acyclic orientation game on random graphs

Noga Alon; Zsolt Tuza

doi:10.1002/rsa.3240060213

The acyclic orientation game on random graphs

Noga Alon, Zsolt Tuza

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

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³n) is established. Graphs G = V, E in which all edges have to be examined are considered, as well.

Original language	English (US)
Pages (from-to)	261-268
Number of pages	8
Journal	Random Structures & Algorithms
Volume	6
Issue number	2-3
DOIs	https://doi.org/10.1002/rsa.3240060213
State	Published - 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1002/rsa.3240060213

Cite this

@article{e6675438a6174e1b9dc8731e0d6b9b39,

title = "The acyclic orientation game on random graphs",

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

author = "Noga Alon and Zsolt Tuza",

year = "1995",

doi = "10.1002/rsa.3240060213",

language = "English (US)",

volume = "6",

pages = "261--268",

journal = "Random Structures & Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "2-3",

}

TY - JOUR

T1 - The acyclic orientation game on random graphs

AU - Alon, Noga

AU - Tuza, Zsolt

PY - 1995

Y1 - 1995

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

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

UR - http://www.scopus.com/inward/record.url?scp=84990662390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990662390&partnerID=8YFLogxK

U2 - 10.1002/rsa.3240060213

DO - 10.1002/rsa.3240060213

M3 - Article

AN - SCOPUS:84990662390

SN - 1042-9832

VL - 6

SP - 261

EP - 268

JO - Random Structures & Algorithms

JF - Random Structures & Algorithms

IS - 2-3

ER -

The acyclic orientation game on random graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this