Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/6306
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 |
URI: | http://www.sciencedirect.com/science/article/pii/S0166218X11004197 http://bura.brunel.ac.uk/handle/2438/6306 |
DOI: | http://dx.doi.org/10.1016/j.dam.2011.10.036 |
ISSN: | 0166-218X |
Appears in Collections: | Publications Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 117.98 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.