Please use this identifier to cite or link to this item:
Title: The complexity of two graph orientation problems
Authors: Eggemann, N
Noble, SD
Keywords: Graph orientation;Diameter;Planar graph;Graph minors;Apex graph
Issue Date: 2012
Publisher: Elsevier
Citation: Discrete Applied Mathematics, 160(4-5): 513 - 517, Mar 2012
Abstract: 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.
Description: This is the post-print version of the Article. The official published version can be accessed from the link below - Copyright @ 2012 Elsevier
ISSN: 0166-218X
Appears in Collections:Publications
Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
Fulltext.pdf117.98 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.