Dimension Métrique des Graphes Orientés

Julien Bensmail 1 Fionn Mc Inerney 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : La dimension métrique MD(G) d'un graphe non-dirigé G est le nombre minimum de sommets qui permettent, via leurs distances à tous les sommets, de distinguer les sommets de G les uns des autres. Cette notion a été beaucoup étudiée depuis sa conception dans les années 70 car elle permet notamment de modéliser la localisation d'une cible par ses distances à un réseau de capteurs dans un graphe. Nous considérons ici sa généralisation aux digraphes. Nous étudions, pour certaines classes de graphes, la dimension métrique maximum parmi toutes les orientations fortement connexes en donnant des bornes sur cette valeur. Notamment, nous étudions ce paramètre dans les graphes de degré maximum borné, les grilles et les tores. Pour ces derniers, nous trouvons la valeur exacte asymptotiquement.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-02118847
Contributor : Fionn Mc Inerney <>
Submitted on : Friday, May 3, 2019 - 1:30:55 PM
Last modification on : Monday, May 6, 2019 - 5:45:51 PM

File

corrected_algotel2019_md_orien...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02118847, version 1

Collections

Citation

Julien Bensmail, Fionn Mc Inerney, Nicolas Nisse. Dimension Métrique des Graphes Orientés. ALGOTEL 2019 - 21èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2019, Saint Laurent de la Cabrerisse, France. ⟨hal-02118847⟩

Share

Metrics

Record views

41

Files downloads

216