Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/6306
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Eggemann, N | - |
dc.contributor.author | Noble, SD | - |
dc.date.accessioned | 2012-03-16T16:38:36Z | - |
dc.date.available | 2012-03-16T16:38:36Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | Discrete Applied Mathematics, 160(4-5): 513 - 517, Mar 2012 | en_US |
dc.identifier.issn | 0166-218X | - |
dc.identifier.uri | http://www.sciencedirect.com/science/article/pii/S0166218X11004197 | en |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/6306 | - |
dc.description | This is the post-print version of the Article. The official published version can be accessed from the link below - Copyright @ 2012 Elsevier | en_US |
dc.description.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. | en_US |
dc.description.sponsorship | This work is partially supported by EC Marie Curie programme NET-ACE (MEST-CT-2004-6724), and Heilbronn Institute for Mathematical Research, Bristol. | en_US |
dc.language.iso | en | en_US |
dc.publisher | Elsevier | en_US |
dc.subject | Graph orientation | en_US |
dc.subject | Diameter | en_US |
dc.subject | Planar graph | en_US |
dc.subject | Graph minors | en_US |
dc.subject | Apex graph | en_US |
dc.title | The complexity of two graph orientation problems | en_US |
dc.type | Article | en_US |
dc.identifier.doi | http://dx.doi.org/10.1016/j.dam.2011.10.036 | - |
pubs.organisational-data | /Brunel | - |
pubs.organisational-data | /Brunel/Brunel Active Staff | - |
pubs.organisational-data | /Brunel/Brunel Active Staff/School of Info. Systems, Comp & Maths | - |
pubs.organisational-data | /Brunel/Brunel Active Staff/School of Info. Systems, Comp & Maths/Maths | - |
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.