LIFO-search: A min-max theorem and a searching game for cycle-rank and tree-depth

Abstract : We introduce a variant of the classic node search game called LIFO-search where searchers are assigned different numbers. The additional rule is that a searcher can be removed only if no searchers of lower rank are in the graph at that moment. We show that all common variations of the game require the same number of searchers. We then introduce the notion of (directed) shelters in (di)graphs and prove a min-max theorem implying their equivalence to the cycle-rank/tree-depth parameter in (di)graphs. As (directed) shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent to the one of cycle-rank/tree-depth in (di)graphs.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804777
Contributeur : Dimitrios M. Thilikos <>
Soumis le : mardi 26 mars 2013 - 12:06:07
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

Citation

Dimitrios M. Thilikos, Archontia C. Giannopoulou, Paul Hunter. LIFO-search: A min-max theorem and a searching game for cycle-rank and tree-depth. Discrete Applied Mathematics, Elsevier, 2012, pp.2089-2097. 〈http://www.sciencedirect.com/science/article/pii/S0166218X12001199〉. 〈10.1016/j.dam.2012.03.015〉. 〈lirmm-00804777〉

Partager

Métriques

Consultations de la notice

136