On the Monotonicity of Process Number |
| |
| Institution: | 1. COATI, INRIA, I3S(CNRS/UNSA), France;2. ParGO - Univ. Federal do Ceará, Brazil;1. Universidad Nacional de Rosario, Argentina;2. CONICET and Universidad Nacional de Rosario, Argentina;3. University of Waterloo, Canada;1. Institute of Math. Sciences, IV Cross Road, Taramani, Chennai 600 113, India;2. School of Comp. Science, Simon Fraser University, Burnaby, Canada V5A 1S6;3. DIMAP and Math. Institute, University of Warwick, Coventry CV4 7AL, UK;1. Institute for Software Technology, University of Technology, Graz, Austria;2. Instituto de Matemáticas, Universidad Nacional Autónoma de México, D.F. México, México |
| |
| 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 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. |
| |
| Keywords: | Graph Searching Process Number Monotonicity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
