The acyclic orientation game on random graphs

DOI10.1002/rsa.3240060213zbMath0821.05049OpenAlexW1995636353MaRDI QIDQ4697816

Zsolt Tuza, Noga Alon

Publication date: 1 May 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240060213

zbMATH Keywords

upper boundacyclic orientationrandom graphtransitive closureedge probabilityacyclic orientation game

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43)

Related Items (3)

Efficient enumeration of graph orientations with sources ⋮ Shattering, graph orientations, and connectivity ⋮ The oriented cycle game

Cites Work

• Parallel comparison algorithms for approximation problems
• Searching for acyclic orientations of graphs
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
• Sorting and Selecting in Rounds
• Sorting, Approximate Sorting, and Searching in Rounds

This page was built for publication: The acyclic orientation game on random graphs