Please use this identifier to cite or link to this item:
|Title:||Minimizing the oriented diameter of a planar graph|
|Keywords:||Diameter;Graph orientation;Graph minors;Planar graph|
|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.|
|Appears in Collections:||Mathematical Science|
Dept of Mathematics Research Papers
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.