Finding an Unknown Acyclic Orientation of a Given Graph

Details Finding an Unknown Acyclic Orientation of a Given Graph Finding an Unknown Acyclic Orientation of a Given Graph

2009-04-07

arxiv.org/abs/0904.1229v1

Mathematics

Combinatorics

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Finding an Unknown Acyclic Orientation of a Given Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding an Unknown Acyclic Orientation of a Given Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding an Unknown Acyclic Orientation of a Given Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-213722