Show simple item record

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorWADE, Ahmed
dc.contributor.editorNisse
dc.contributor.editorNicolas and Rousseau
dc.contributor.editorFranck and Busnel
dc.contributor.editorYann
dc.date.accessioned2024-04-15T09:43:27Z
dc.date.available2024-04-15T09:43:27Z
dc.date.issued2013
dc.date.conference2013-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197767
dc.description.abstractDans cet article, nous étudions les graphes dynamiques T-intervalle-connexes du point de vue du temps nécessaire à leur exploration par une entité mobile (agent). Un graphe dynamique est T-intervalle-connexe (T >= 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 connexion au cours du temps a été introduite par Kuhn, Lynch et Oshman (STOC 2010). Nous nous concentrons sur le cas où le graphe sous-jacent est un anneau de taille n et nous montrons que la complexité en temps en pire cas est de 2n-T-Theta(1) unités de temps si l'agent connaît la dynamique du graphe, et n+ n/max{1,T-1} (delta-1) +- 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.source.title15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
dc.subjectGraphe dynamique
dc.subjectexploration
dc.subjectT-intervalle-connexité
dc.subjectagent mobile
dc.titleExploration des graphes dynamiques $T$-intervalle-connexes : le cas de l'anneau
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page73-76
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
bordeaux.countryFR
bordeaux.title.proceeding15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
bordeaux.conference.cityPornic
bordeaux.peerReviewedoui
hal.identifierhal-00818450
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00818450v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Exploration%20des%20graphes%20dynamiques%20$T$-intervalle-connexes%20:%20le%20cas%20de%20l'anneau&rft.btitle=15%C3%A8mes%20Rencontres%20Francophones%20sur%20les%20Aspects%20Algorithmiques%20des%20T%C3%A9l%C3%A9communications%20(AlgoTel)&rft.atitle=Exploration%20des%20graphes%20dynamiques%20$T$-intervalle-connexes%20:%20le%20cas%20de%20l'anneau&rft.date=2013&rft.spage=73-76&rft.epage=73-76&rft.au=ILCINKAS,%20David&WADE,%20Ahmed&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record