The complexity of two graph orientation problems

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. Our main result is that for each positive integer k, there is a linear-time algorithm that decides for a planar graph Gwhether there is an orient...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2012-03, Vol.160 (4-5), p.513-517
Main Authors: Eggemann, Nicole, Noble, Steven D.
Format: Article
Language:English
Subjects:
Algorithms
Apex graph
Diameter
Graph minors
Graph orientation
Graphs
Integers
Mathematical analysis
Minimization
Optimization
Orientation
Planar graph
Shortest-path problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. Our main result is that for each positive integer k, there is a linear-time algorithm that decides for a planar graph Gwhether 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 F not containing all apex graphs. In contrast, it is known to be NP-complete to decide whether a graph has an orientation such that the sum of all the shortest path lengths is at most an integer specified in the input. We give a simpler proof of this result.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2011.10.036