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.
Type de document :
Communication dans un congrès
David and Sebastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.29-32, 2008
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00374450
Contributeur : David Coudert <>
Soumis le : mercredi 8 avril 2009 - 17:02:06
Dernière modification le : jeudi 11 janvier 2018 - 06:20:36
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 16:27:11

Fichier

08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00374450, version 1

Citation

Nicolas Nisse, Karol Suchan. Voleur véloce dans un réseau planaire. David and Sebastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.29-32, 2008. 〈inria-00374450〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

42