Minimizing the oriented diameter of a planar graph

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/3829

Full metadata record

DC Field	Value	Language
dc.contributor.author	Eggemann, N	-
dc.contributor.author	Noble, SD	-
dc.coverage.spatial	5	-
dc.date.accessioned	2009-11-11T14:22:49Z	-
dc.date.available	2009-11-11T14:22:49Z	-
dc.date.issued	2009	-
dc.identifier.citation	Electronic Notes in Discrete Mathematics. 34: 267-271	en
dc.identifier.issn	1571-0653	-
dc.identifier.uri	http://www.sciencedirect.com/science/article/pii/S1571065309000857	en
dc.identifier.uri	http://bura.brunel.ac.uk/handle/2438/3829	-
dc.description.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.	en
dc.language.iso	en	en
dc.publisher	Elsevier	en
dc.subject	Diameter	en
dc.subject	Graph orientation	en
dc.subject	Graph minors	en
dc.subject	Planar graph	en
dc.title	Minimizing the oriented diameter of a planar graph	en
dc.type	Research Paper	en
dc.identifier.doi	http://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	Size	Format
Fulltext.pdf		140.13 kB	Adobe PDF	View/Open