Sascha Kurz ; Martin Laetsch - Bounds for the minimum oriented diameter

dmtcs:567 - Discrete Mathematics & Theoretical Computer Science, May 13, 2012, Vol. 14 no. 1 -
Bounds for the minimum oriented diameter

Authors: Sascha Kurz ; Martin Laetsch

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).

Volume: Vol. 14 no. 1
Section: Graph and Algorithms
Published on: May 13, 2012
Accepted on: June 9, 2015
Submitted on: September 15, 2010
Keywords: diameter,orientation,domination,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Consultation statistics

This page has been seen 170 times.
This article's PDF has been downloaded 376 times.