A min-max theorem for LIFO-search

Archontia C. Giannopoulou; Dimitrios M. Thilikos

doi:10.1016/j.endm.2011.09.064

A min-max theorem for LIFO-search

Archontia C. Giannopoulou, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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 introduce the notion of shelters in graphs and we prove a min-max theorem implying their equivalence with the tree-depth parameter. As shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent with the one of tree-depth.

Original language	English (US)
Pages (from-to)	395-400
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	38
DOIs	https://doi.org/10.1016/j.endm.2011.09.064
State	Published - Dec 1 2011

Keywords

Graph Searching
Obstructions
Tree-depth
Width Parameters

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2011.09.064

Cite this

@article{9e60393919c440f89823881f404004ba,

title = "A min-max theorem for LIFO-search",

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 introduce the notion of shelters in graphs and we prove a min-max theorem implying their equivalence with the tree-depth parameter. As shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent with the one of tree-depth.",

keywords = "Graph Searching, Obstructions, Tree-depth, Width Parameters",

author = "Giannopoulou, {Archontia C.} and Thilikos, {Dimitrios M.}",

year = "2011",

month = dec,

day = "1",

doi = "10.1016/j.endm.2011.09.064",

language = "English (US)",

volume = "38",

pages = "395--400",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - A min-max theorem for LIFO-search

AU - Giannopoulou, Archontia C.

AU - Thilikos, Dimitrios M.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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 introduce the notion of shelters in graphs and we prove a min-max theorem implying their equivalence with the tree-depth parameter. As shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent with the one of tree-depth.

AB - 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 introduce the notion of shelters in graphs and we prove a min-max theorem implying their equivalence with the tree-depth parameter. As shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent with the one of tree-depth.

KW - Graph Searching

KW - Obstructions

KW - Tree-depth

KW - Width Parameters

UR - http://www.scopus.com/inward/record.url?scp=82955192455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=82955192455&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2011.09.064

DO - 10.1016/j.endm.2011.09.064

M3 - Article

AN - SCOPUS:82955192455

SN - 1571-0653

VL - 38

SP - 395

EP - 400

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

A min-max theorem for LIFO-search

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this