کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418392 | 681664 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
LIFO-search: A min–max theorem and a searching game for cycle-rank and tree-depth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2089–2097
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2089–2097
نویسندگان
Archontia C. Giannopoulou, Paul Hunter, Dimitrios M. Thilikos,