Afficher la notice abrégée

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorWADE, Ahmed
dc.date.accessioned2024-04-15T09:41:37Z
dc.date.available2024-04-15T09:41:37Z
dc.date.created2013-04-25
dc.date.issued2013-04-25
dc.date.conference2013-05-25
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197613
dc.description.abstractDans cet article, nous étudions le problème d'exploration, par une entité mobile (agent), des graphes dynamiques T-intervalle-connexes qui ont comme graphe sous-jacent un anneau de taille $n$. Un graphe dynamique est T-intervalle-connexe ($T \geq 1$) si pour chaque fenêtre de $T$ unités de temps, il existe un sous-graphe couvrant connexe stable. Cette propriété de stabilité de graphes dynamiques a été introduite par Kuhn, Lynch et Oshman~\cite{KLO10} (STOC 2010). Nous montrons que la complexité au pire cas est de $2n-T-\Theta(1)$ unités de temps si l'agent connaît la dynamique du graphe, et $\frac{n}{\max\{1, T-1\} } (\delta-1) +n \pm \Theta(\delta)$ unités de temps sinon, où $\delta$ est le temps maximum entre deux apparitions successives d'une arête.
dc.description.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isofr
dc.subjectGraphes dynamiques
dc.subjectAgent mobile
dc.subjectT-intervalle-connexité
dc.subjectExploration
dc.titleExploration des graphes dynamiques T-intervalle-connexes
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Complexité [cs.CC]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Robotique [cs.RO]
dc.subject.halMathématiques [math]/Combinatoire [math.CO]
bordeaux.page78-85
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleCNRIA 2013 - 5ème Colloque National sur la Recherche en Informatique et ses Applications
bordeaux.countrySN
bordeaux.conference.cityZinguichor
bordeaux.peerReviewedoui
hal.identifierhal-00965933
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2013-05-27
hal.popularnon
hal.audienceNationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00965933v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Exploration%20des%20graphes%20dynamiques%20T-intervalle-connexes&rft.atitle=Exploration%20des%20graphes%20dynamiques%20T-intervalle-connexes&rft.date=2013-04-25&rft.spage=78-85&rft.epage=78-85&rft.au=WADE,%20Ahmed&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée