کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654086 | 1632808 | 2011 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimal guard sets and the Helly property
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In a set system FF, a guard set of an F∈FF∈F is a subset B⊆FB⊆F such that BB intersects all those F′∈FF′∈F which meet FF but are not contained in FF. Given a graph GG, we consider set systems FF whose intersection graph is GG, and determine one such FF in which the guard sets of all F∈FF∈F are as small as possible. We prove that the minimum–both in global and local sense–is attained by the dual of the clique hypergraph of GG, a structure which also played an important role in the proof of the Perfect Graph Theorem. We also put some remarks concerning algorithmic complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 32, Issue 1, January 2011, Pages 28–32
Journal: European Journal of Combinatorics - Volume 32, Issue 1, January 2011, Pages 28–32
نویسندگان
Gábor Bacsó, Zsolt Tuza,