Connected Surveillance Game

Résumé : Le jeu de surveillance [Fomin \emph{et al.}, 2012] modélise le problème de préchargement des documents web comme un jeu de poursuite dans un graphe. Ce jeu se joue tour par tour à deux joueurs. Le premier joueur, appelé l'\emph{observateur}, peut marquer un nombre $k$ prédéfini (et constant) de sommets à chaque tour. Le deuxième joueur commande un \emph{surfeur} qui se déplace sur les sommets du graphe en suivant les arêtes. Le surfeur commence à un sommet prédéfini du graphe, initialement marqué. Son objectif est d'atteindre un noeud non marqué avant que tous les noeuds du graphe soient marqués. L'indice de surveillance $\sn(G)$ d'un graphe $G$ est le nombre $k$ minimum de noeuds que l'observateur doit marquer à chaque tour en s'assurant qu'il gagne quelle que soit la trajectoire du surfeur dans $G$. Fomin \emph{et al.} ont également défini le jeu de surveillance connexe où l'observateur doit s'assurer que l'ensemble des noeuds marqués induit toujours un sous-graphe connexe. Ils demandent quel est le coût de la connectivité, c'est-à-dire, existe-t-il une constante $c >0$ telle que le rapport (ou la différence) entre l'indice de surveillance connexe $\csn(G)$ et $\sn(G)$ est au plus $c$ pour tout graphe $G$. Il est facile de montrer que $\csn(G) \leq \Delta \sn(G)$ pour tout graphe $G$ de degré maximum $\Delta$. En outre, il a été démontré qu'il existe des graphes $G$ pour lesquels $\csn(G) = \sn(G) + 1$. Dans cet article, nous examinons la question du coût de la connectivité. Nous présentons d'abord de nouvelles bornes supérieures et inférieures non triviales pour le coût de la connectivité dans le jeu de surveillance. Plus précisément, nous présentons une famille de graphes $G$ tels que $\csn(G) > \sn(G) + 1$. De plus, nous prouvons que $\csn(G) \leq \sn(G) \sqrt{n}$ pour tout graphe $G$ avec $n$-noeuds. Nous définissons ensuite le \emph{jeu de surveillance en ligne} où l'observateur n'a pas \emph{a priori} connaissance de la topologie du graphe et la découvre peu à peu. Cette variante, qui s'adapte mieux à la motivation du préchargement, est une restriction de la variante connexe. Malheureusement, nous montrons que tout algorithme pour résoudre le jeu de la surveillance en ligne a un rapport compétitif au mieux de $\Omega(\Delta)$. Autrement dit, cette variante, intéressante en soi, ne permet pas d'obtenir de meilleures bornes supérieures pour la variante connexe.
Type de document :
Rapport
[Research Report] RR-8297, INRIA. 2013, pp.22


https://hal.inria.fr/hal-00820271
Contributeur : Ronan Pardo Soares <>
Soumis le : vendredi 3 mai 2013 - 15:29:27
Dernière modification le : vendredi 16 septembre 2016 - 15:19:48
Document(s) archivé(s) le : dimanche 4 août 2013 - 04:05:41

Fichier

RR-8297.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00820271, version 1

Collections

Citation

Frédéric Giroire, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, Ronan Pardo Soares. Connected Surveillance Game. [Research Report] RR-8297, INRIA. 2013, pp.22. <hal-00820271>

Exporter

Partager

Métriques

Consultations de
la notice

324

Téléchargements du document

166