Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Bounds for the minimum oriented diameter

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).
Document type :
Journal articles
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990564
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:19:34 PM
Last modification on : Friday, October 13, 2017 - 5:08:16 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:49:25 PM

File

1745-6917-2-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

135

Files downloads

809