1Mathematisches Institut [Bayreuth] (University of Bayreuth Faculty of Mathematics, Physics and Computer Science Mathematical Institute D-95440 Bayreuth Germany - Allemagne)
Abstract : 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).
https://hal.inria.fr/hal-00990564
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s
<>
Soumis le : mardi 13 mai 2014 - 16:19:34
Dernière modification le : vendredi 13 octobre 2017 - 17:08:16
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:49:25
