کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428752 686904 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improved algorithms for recognizing p-Helly and hereditary p-Helly hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Improved algorithms for recognizing p-Helly and hereditary p-Helly hypergraphs
چکیده انگلیسی

A hypergraph H is set of vertices V together with a collection of nonempty subsets of it, called the hyperedges of H. A partial hypergraph of H is a hypergraph whose hyperedges are all hyperedges of H, whereas for V′⊆V the subhypergraph (induced by V′) is a hypergraph with vertices V′ and having as hyperedges the subsets obtained as nonempty intersections of V′ and each of the hyperedges of H. For p⩾1 say that H is p-intersecting when every subset formed by p hyperedges of H contain a common vertex. Say that H is p-Helly when every p-intersecting partial hypergraph H′ of H contains a vertex belonging to all the hyperedges of H′. A hypergraph is hereditary p-Helly when every (induced) subhypergraph of it is p-Helly. In this paper we describe new characterizations for hereditary p-Helly hypergraphs and discuss the recognition problems for both p-Helly and hereditary p-Helly hypergraphs. The proposed algorithms improve the complexity of the existing recognition algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 4, 31 October 2008, Pages 247-250