Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
School of Information Systems, Computing and Mathematics Research Papers >

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
Publication 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:School of Information Systems, Computing and Mathematics Research Papers
Mathematical Science

Files in This Item:

File Description SizeFormat
Fulltext.pdf140.13 kBAdobe PDFView/Open

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

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan