Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00374450
Contributor : David Coudert <>
Submitted on : Wednesday, April 8, 2009 - 5:02:06 PM
Last modification on : Wednesday, May 6, 2020 - 8:18:02 PM
Long-term archiving on: : Friday, October 12, 2012 - 4:27:11 PM

File

08.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00374450, version 1

Citation

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⟩

Share

Metrics

Record views

146

Files downloads

167