On The Monotonicity of Process Number

Nicolas Nisse 1 Ronan Soares 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Les jeux de capture impliquent une équipe d'agents qui doivent capturer un fugitif se déplaçant dans un graphe. Ces jeux ont été très étudiés pour leur interprétation en termes de décompositions de graphes (tree-decomposition, path-decomposition). Dans le but de définir de "bonnes" décompositions pour les graphes orientés, des jeux similaires ont été définis et étudiés dans les graphes orientés. Dans ce travail, nous considérons un jeu qui a été défini dans le contexte du routage dans les réseaux WDM. Dans ce jeu, le processing game, le fugitif est invisible, arbitrairement rapide et se déplace dans le sens opposé des arcs. De plus, le fugitif est capturé dès qu'il lui est impossible d'accéder à une composante fortement connexe sans agents. Nous prouvons que ce jeu est monotone. Cela permet de montrer l'équivalence du processing game et d'une nouvelle décomposition de graphes orientés.
Type de document :
Rapport
[Research Report] RR-8132, INRIA. 2012, pp.17


https://hal.inria.fr/hal-00745587
Contributeur : Ronan Pardo Soares <>
Soumis le : mardi 13 novembre 2012 - 12:45:29
Dernière modification le : samedi 17 septembre 2016 - 01:35:48

Fichier

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

Identifiants

  • HAL Id : hal-00745587, version 1

Collections

Citation

Nicolas Nisse, Ronan Soares. On The Monotonicity of Process Number. [Research Report] RR-8132, INRIA. 2012, pp.17. <hal-00745587>

Exporter

Partager

Métriques

Consultations de
la notice

162

Téléchargements du document

104