Bounds for the minimum oriented diameter - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2012

Bounds for the minimum oriented diameter

Résumé

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).
Fichier principal
Vignette du fichier
1745-6917-2-PB.pdf (469.59 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00990564 , version 1 (13-05-2014)

Identifiants

Citer

Sascha Kurz, Martin Laetsch. Bounds for the minimum oriented diameter. Discrete Mathematics and Theoretical Computer Science, 2012, Vol. 14 no. 1 (1), pp.109-140. ⟨10.46298/dmtcs.567⟩. ⟨hal-00990564⟩

Collections

TDS-MACS
156 Consultations
1013 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More