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.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.editorMathieu
dc.contributor.editorFabien et Hanusse
dc.contributor.editorNicolas
dc.date.accessioned2024-04-15T09:45:28Z
dc.date.available2024-04-15T09:45:28Z
dc.date.issued2012
dc.date.conference2012
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197922
dc.description.abstractNous étudions le problème de l'exploration, par une entité mobile, d'une classe de graphes dynamiques appelés graphes périodiquement variables (PV-graphes). Ils sont définis par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau, et modélisent donc naturellement les réseaux de transport public. Flocchini, Mans et Santoro [FMS09] ont étudié ce problème dans le cas où l'agent doit toujours rester sur les transporteurs. Dans ce papier, nous étudions l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins Theta(p), et la complexité en temps passe de Theta(kp^2) à Theta(np), où n est le nombre de stations, k le nombre de transporteurs, et p la période maximale (n <= kp dans tout PV-graphe connexe). Par ailleurs, l'algorithme que nous proposons pour prouver les bornes supérieures permet de réaliser la cartographie du PV-graphe, en plus de l'explorer.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isofr
dc.source.titleAlgoTel
dc.subjectExploration
dc.subjectGraphes dynamiques
dc.subjectAgent mobile
dc.subjectPV-graphes
dc.titlePuissance de l'attente aux stations pour l'exploration des réseaux de transport public
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page107-110
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title14èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
bordeaux.countryFR
bordeaux.title.proceedingAlgoTel
bordeaux.conference.cityLa Grande Motte
bordeaux.peerReviewedoui
hal.identifierhal-00691015
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00691015v1
bordeaux.COinSctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.title=Puissance%20de%20l'attente%20aux%20stations%20pour%20l'exploration%20des%20r%C3%A9seaux%20de%20transport%20public&amp;rft.btitle=AlgoTel&amp;rft.atitle=Puissance%20de%20l'attente%20aux%20stations%20pour%20l'exploration%20des%20r%C3%A9seaux%20de%20transport%20public&amp;rft.date=2012&amp;rft.spage=107-110&amp;rft.epage=107-110&amp;rft.au=ILCINKAS,%20David&amp;WADE,%20Ahmed&amp;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