On The Monotonicity of Process Number

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.
Document type :
Reports
[Research Report] RR-8132, 2012, pp.17


https://hal.inria.fr/hal-00745587
Contributor : Ronan Pardo Soares <>
Submitted on : Tuesday, November 13, 2012 - 12:45:29 PM
Last modification on : Tuesday, November 13, 2012 - 2:02:01 PM

File

RR-8132.pdf
fileSource_public_author

Identifiers

  • HAL Id : hal-00745587, version 1

Collections

Citation

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

Export

Share

Metrics

Consultation de
la notice

94

Téléchargement du document

52