Voleur véloce dans un réseau planaire - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Voleur véloce dans un réseau planaire

Résumé

Le jeu des gendarmes et du voleur impliquent deux joueurs qui jouent à tour de rôle dans un réseau. Le premier déplace les gendarmes le long des liens du réseau, puis c'est au tour du second qui déplace le voleur. Le but des gendarmes est d'attraper le voleur, tandis que ce dernier essaie d'éviter la capture indéfiniment. Le problème dans ce contexte est de minimiser le nombre de gendarmes nécessaires pour capturer le voleur. Ce nombre s'appelle l'indice d'évasion du réseau. Si les gendarmes et le voleur ont la même vitesse, Schroder (2001) a prouvé que 3+ 3g/2 gendarmes suffisent à capturer tout voleur dans un réseau de genre borné g. En particulier, cela signifie que la capture d'un voleur dans un réseau planaire est facile puisque 3 gendarmes suffisent (en fait deux gendarmes sont suffisants dans toute grille). Dans ce papier, nous aidons le voleur en lui permettant de se déplacer plus vite que les gendarmes. Nous montrons que cela conduit à une augmentation drastique du nombre de gendarmes. Plus précisement, nous prouvons que $\Omega(\sqrt{\log n})$ gendarmes sont nécessaires pour capturer un voleur véloce dans une grille carrée de côté n. La preuve que nous proposons consiste en une élégante et simple stratégie d'évasion pour le voleur. Il est alors intéressant de savoir si le fait qu'un réseau planaire H ait un indice d'évasion élevé est lié au fait que H contient une large grille G. Nous montrons que ce n'est pas le cas lorsque la notion de contenance correspond à la notion de minoration topologique (c'est à dire si G peut être obtenu de H en remplaçant des chemins dont les sommets internes sont de degré deux, par des arêtes). Cependant, nous prouvons que si H planaire contient une large grille comme sous-graphe induit, alors son indice d'évasion est élevé. Notons que ce dernier résultat n'est pas vrai dans le cas d'un réseau H non planaire.
Fichier principal
Vignette du fichier
08.pdf (99.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00374450 , version 1 (08-04-2009)

Identifiants

  • HAL Id : inria-00374450 , version 1

Citer

Nicolas Nisse, Karol Suchan. Voleur véloce dans un réseau planaire. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.29-32. ⟨inria-00374450⟩
66 Consultations
80 Téléchargements

Partager

Gmail Facebook X LinkedIn More