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) ≤ (1/4 + o(1))n2 for any graph G on n vertices, answering in the affirmative a question of Aigner, Triesch and Tuza [Discrete Mathematics144 (1995) 3–10]. Also, we show that, for every ϵ 0, it is NP-hard to approximate the parameter c(G) within a multiplicative factor 74/73 − ϵ. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1017/S0963548309990289 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
complete graph,n vertex,unknown acyclic orientation,n number,multiplicative factor,worst case,graph g,discrete mathematics144,smallest number | Journal | 19 |
Issue | ISSN | Citations |
1 | 0963-5483 | 0 |
PageRank | References | Authors |
0.34 | 11 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Oleg Pikhurko | 1 | 318 | 47.03 |