Exclusive Graph Searching vs. Pathwidth

Euripides Markou 1 Nicolas Nisse 2 Stéphane Pérennes 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Dans les jeux de capture (Graph Searching), une équipe d'agents doit capturer un fugitif invisible se déplaçant rapidement dans un graphe. De façon équivalente, les agents doivent nettoyer un réseau contaminé. Le problème est de calculer le nombre minimum d'agents nécessaires pour accomplir cette tache. Plusieurs variantes de ces jeux ont été étudiés pour leur lien avec la pathwidth des graphes. Blin et al. ont défini le jeu de capture exclusif dans lequel les agents ne peuvent ni "sauter", ni occuper un sommet à plusieurs. Dans ce rapport, nous étudions la complexité de cette nouvelle variante. Nous montrons que le problème est NP-difficile dans les graphes planaires avec degré au plus 3 et qu'il peut être résolu en temps linéaire dans la classe des cographes. Nous montrons également que la variante monotone du jeu exclusif est NP-complet dans la classe des split-graphes où la pathwidth est NP-complet. De plus, nous prouvons que le jeu exclusif monotone peut être calculé en temps polynomial dans une classe de star-like graphes où calculer la pathwidth est NP-complet. Les complexités de la pathwidth et du jeu de capture exclusif monotone ne peuvent donc être comparées. Il s'agit de la première variante de jeu de capture où une telle différence est avérée
Type de document :
Rapport
[Research Report] RR-8523, INRIA. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00980877
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 18 avril 2014 - 22:25:12
Dernière modification le : samedi 17 septembre 2016 - 01:36:49
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:27:51

Fichier

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

Identifiants

  • HAL Id : hal-00980877, version 1

Collections

Citation

Euripides Markou, Nicolas Nisse, Stéphane Pérennes. Exclusive Graph Searching vs. Pathwidth. [Research Report] RR-8523, INRIA. 2014. 〈hal-00980877〉

Partager

Métriques

Consultations de
la notice

250

Téléchargements du document

239