• 1 Mathematisches Institut [Bayreuth]
• 2 Zentrum für Angewandte Informatik [Köln]

Graphs and Algorithms

[en]
We consider the problem of determining an orientation with minimum diameter MOD(G) of a connected and bridge-less graph G. In 2001 Fomin et al. discovered the relation MOD(G) <= 9 gamma(G) - 5 between the minimum oriented diameter and the size gamma(G) of a minimum dominating set. We improve their upper bound to MOD(G) <= 4 gamma(G).