Please use this identifier to cite or link to this item: http://buratest.brunel.ac.uk/handle/2438/3829
Full metadata record
DC FieldValueLanguage
dc.contributor.authorEggemann, N-
dc.contributor.authorNoble, SD-
dc.coverage.spatial5-
dc.date.accessioned2009-11-11T14:22:49Z-
dc.date.available2009-11-11T14:22:49Z-
dc.date.issued2009-
dc.identifier.citationElectronic Notes in Discrete Mathematics. 34: 267-271en
dc.identifier.issn1571-0653-
dc.identifier.urihttp://www.sciencedirect.com/science/article/pii/S1571065309000857en
dc.identifier.urihttp://bura.brunel.ac.uk/handle/2438/3829-
dc.description.abstractWe 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.en
dc.language.isoenen
dc.publisherElsevieren
dc.subjectDiameteren
dc.subjectGraph orientationen
dc.subjectGraph minorsen
dc.subjectPlanar graphen
dc.titleMinimizing the oriented diameter of a planar graphen
dc.typeResearch Paperen
dc.identifier.doihttp://dx.doi.org/10.1016/j.endm.2009.07.043-
Appears in Collections:Dept of Mathematics Research Papers
Mathematical Sciences

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.