کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418662 | 681703 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The fast robber on interval and chordal graphs
ترجمه فارسی عنوان
دزدی سریع در فاصله و نمودارهای هوستر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study a variant of the Cops and Robber game in which the robber has unbounded speed, i.e. can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let c∞(G)c∞(G) denote the number of cops needed to capture the robber in graph GG in this variant. We show that if GG is an interval graph, then c∞(G)∈O(|V(G)|); while for every nn there exists an nn-vertex chordal graph GG with c∞(G)∈Ω(n/logn)c∞(G)∈Ω(n/logn). This indicates a large contrast between interval graphs and chordal graphs in this variant, whereas in the original Cops and Robber game a single cop suffices for both classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 180, 10 January 2015, Pages 188–193
Journal: Discrete Applied Mathematics - Volume 180, 10 January 2015, Pages 188–193
نویسندگان
Abbas Mehrabian,