Finding an unknown acyclic orientation of a given graph

DOI10.1017/S0963548309990289MaRDI QIDQ3557528zbMATH OpenFDO

Authors 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

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

Abstract: Let c(G) be the smallest number of edges we have to test in order to determine an unknown acyclic orientation of the given graph G in the worst case. For example, if G is the complete graph on n vertices, then c(G) is the smallest number of comparisons needed to sort n numbers. We prove that c(G)le (1/4+o(1))n^2 for any graph G on n vertices, answering in the affirmative a question of Aigner, Triesch, and Tuza [Discrete Mathematics, 144 (1995) 3-10]. Also, we show that, for every e>0, it is NP-hard to approximate the parameter c(G) within a multiplicative factor 74/73-e.

Recommendations

• The acyclic orientation game on random graphs
• Generating the Acyclic Orientations of a Graph
• Searching for acyclic orientations of graphs
• Graph orientations and linear extensions
• Transitive Orientations of Graphs

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Tournament Problem
• Constant time parallel sorting: An empirical view.
• Gadgets, Approximation, and Linear Programming
• New results in minimum-comparison sorting
• Parallel Sorting with Constant Time for Comparisons
• Parallelism in Comparison Problems
• Searching for acyclic orientations of graphs
• Some optimal inapproximability results
• Sorting in one round
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem

Cited in

(1)

• Efficient enumeration of graph orientations with sources

This page was built for publication: Finding an unknown acyclic orientation of a given graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557528)