Finding an unknown acyclic orientation of a given graph
From MaRDI portal
Publication:3557528
DOI10.1017/S0963548309990289zbMATH Open1209.05113arXiv0904.1229MaRDI QIDQ3557528FDOQ3557528
Authors: Oleg Pikhurko 
Publication date: 23 April 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0904.1229
Recommendations
Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38)
Cites Work
- Title not available (Why is that?)
- New results in minimum-comparison sorting
- 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
- Sorting in one round
- The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
- Parallel Sorting with Constant Time for Comparisons
- A Tournament Problem
- Constant time parallel sorting: An empirical view.
- Searching for acyclic orientations of graphs
Cited In (1)
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)
