Finding an Unknown Acyclic Orientation of a Given Graph

DOI10.1017/S0963548309990289zbMath1209.05113arXiv0904.1229MaRDI QIDQ3557528

Oleg Pikhurko

Publication date: 23 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.1229

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

Efficient enumeration of graph orientations with sources

Cites Work

• Unnamed Item
• Sorting in one round
• Constant time parallel sorting: An empirical view.
• New results in minimum-comparison sorting
• Searching for acyclic orientations of graphs
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• Parallel Sorting with Constant Time for Comparisons
• Parallelism in Comparison Problems
• Gadgets, Approximation, and Linear Programming
• Some optimal inapproximability results
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Tournament Problem