کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10332152 687156 2005 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Helly property on subfamilies of limited size
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The Helly property on subfamilies of limited size
چکیده انگلیسی
In this work we consider the problem of determining whether a hypergraph has the p-Helly property, when the considered subfamilies are limited by a size k. That is, whether every partial hypergraph with at most k edges is p-Helly. Further, we study the related problem applied to the cliques of a graph. In all cases, depending on the values of p and k, either we show that the problem can be solved in polynomial time, or we describe a NP-hardness proof.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 93, Issue 2, 31 January 2005, Pages 53-56
نویسندگان
, , ,