Mathematics – Combinatorics
Scientific paper
2010-04-14
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.
Eggemann Nicole
Noble Steven D.
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-528400