On The Monotonicity of Process Number

Description

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 tree- and path-decomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such 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, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has 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.

Abstract (French)

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.

Additional details