The Complexity of Two Graph Orientation Problems

Details The Complexity of Two Graph Orientation Problems The Complexity of Two Graph Orientation Problems

2010-04-14

arxiv.org/abs/1004.2478v1

Mathematics

Combinatorics

9 pages

Scientific paper

We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-complete to decide whether a graph has an orientation such that the sum of all the shortest paths lengths is at most an integer specified in the input. The proof is a short reduction from a result of Chv\'atal and Thomassen showing that it is NP-complete to decide whether a graph can be oriented so that its diameter is at most 2. In contrast, for each positive integer k, we describe a linear-time algorithm that decides for a planar graph G whether there is an orientation for which the diameter is at most k. We also extend this result from planar graphs to any minor-closed family not containing all apex graphs.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Two Graph Orientation Problems 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 The Complexity of Two Graph Orientation Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Two Graph Orientation Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-528400