Reconstruire un graphe en une ronde

Florent Becker 1 Martin Matamala 2, 3 Nicolas Nisse 4 Ivan Rapaport 3, 2 Karol Suchan 5 Ioan Todinca 1
1 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans
2 CMM - Centro de Modelamiento Matemático
3 DIM - Departamento de Ingeniería Matemática [Santiago]
4 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
5 Facultad de Ingeniería y Ciencias [Santiago]
Résumé : Nous étudions quelles propriétés d'un réseau peuvent être calculées à partir d'une petite quantité d'informations locales fournie par ses noeuds. Notre modèle est une restriction de CONGEST, un modèle distribué classique. Il est proche du modèle de complexité de communication avec messages simultanés de Babai et al. Chacun des n noeuds --qui ne connaissent que leur identifiant, ceux de leurs voisins et la taille du graphe-- envoie un message de taille O(log(n)) bits à une entité centrale, le superviseur. Celui-ci doit alors déterminer une certaine propriété du réseau. Nous montrons que des questions telles que: ''Est-ce que le graphe contient un triangle? un carré ? Quel est son diamètre?" ne peuvent pas être résolues dans ce modèle. En revanche, pour de nombreuses classes de graphes : celles de dégénérescence bornée (incluant les graphes planaires, ceux de largeur arborescente bornée... ), les sommets peuvent succinctement donner une description complète du graphe au superviseur. Nous laissons ouverte la question de décider la connexité.
Type de document :
Communication dans un congrès
Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00587250
Contributeur : Nicolas Nisse <>
Soumis le : mardi 19 avril 2011 - 19:51:30
Dernière modification le : mercredi 14 décembre 2016 - 01:03:29
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 16:50:18

Fichier

alg4pUTF8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00587250, version 1

Collections

ALGOTEL2011 | INRIA | UNIV-ORLEANS | I3S | MSL | UNICE | MSL-THESE | TDS-MACS

Citation

Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, et al.. Reconstruire un graphe en une ronde. Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. 2011. <inria-00587250>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

464

Téléchargements du document

114

Contact


archive-ouverte@inria.fr