Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/3829
Title: | Minimizing the oriented diameter of a planar graph |
Authors: | Eggemann, N Noble, SD |
Keywords: | Diameter;Graph orientation;Graph minors;Planar graph |
Issue Date: | 2009 |
Publisher: | Elsevier |
Citation: | Electronic Notes in Discrete Mathematics. 34: 267-271 |
Abstract: | We consider the problem of minimizing the diameter of an orientation of a planar graph. A result of Chvátal and Thomassen shows that for general graphs, it is NP-complete to decide whether a graph can be oriented so that its diameter is at most two. In contrast to this, for each constant l, we describe an algorithm that decides if a planar graph G has an orientation with diameter at most l and runs in time O(c|V|), where c depends on l. |
URI: | http://www.sciencedirect.com/science/article/pii/S1571065309000857 http://bura.brunel.ac.uk/handle/2438/3829 |
DOI: | http://dx.doi.org/10.1016/j.endm.2009.07.043 |
ISSN: | 1571-0653 |
Appears in Collections: | Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 140.13 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.