On the Monotonicity of Process Number

Nicolas Nisse 1 Ronan Pardo Soares 2
1 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
Abstract : Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with the tree-and the path-decomposition of graphs. In order to define de-compositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks. Namely, in the processing game, the fugitive is invisible, arbitrarily fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it can access to a strongly connected component free of searchers. We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2016, Discrete Applied Mathematics, 210, pp.103-111
Liste complète des métadonnées

Contributeur : Nicolas Nisse <>
Soumis le : mercredi 13 juillet 2016 - 13:04:57
Dernière modification le : mercredi 14 décembre 2016 - 01:03:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01345240, version 1



Nicolas Nisse, Ronan Pardo Soares. On the Monotonicity of Process Number. Discrete Applied Mathematics, Elsevier, 2016, Discrete Applied Mathematics, 210, pp.103-111. <hal-01345240>



Consultations de
la notice


Téléchargements du document