Finding an Unknown Acyclic Orientation of a Given Graph
| dc.creator | Pikhurko, Oleg | |
| dc.date | 2009-04-07 | |
| dc.date.accessioned | 2026-07-07T13:01:38Z | |
| dc.date.available | 2026-07-07T13:01:38Z | |
| dc.description | 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. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0904.1229 | |
| dc.identifier | http://arxiv.org/abs/0904.1229 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226212 | |
| dc.subject | Combinatorics | |
| dc.subject | Information Theory | |
| dc.subject | 68P10 | |
| dc.title | Finding an Unknown Acyclic Orientation of a Given Graph | |
| dc.type | text |