کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871791 1440191 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Inapproximability results and bounds for the Helly and Radon numbers of a graph
ترجمه فارسی عنوان
نتایج غیر قابل دستیابی و محدوده برای اعداد هلی و رادون یک گراف
کلمات کلیدی
نمودار دو طرفه، محدب جغرافیایی، شماره هلی، غیر قابل پیش بینی بودن تعداد رادون، کران بالا،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let C be a convexity on a set X and denote the convex hull of S⊆X in C by H(S). The Helly number (Radon number) of C is the minimum integer k such that, for every S⊆X with at least k+1 elements, it holds ⋂v∈SH(S∖{v})≠∅ (there is a bipartition of S into sets S1 and S2 with H(S1)∩H(S2)≠∅). In this work, we show that there is no approximation algorithm for the Helly or the Radon number of a graph G of order n in the geodetic convexity to within a factor n1−ε for any ε>0, unless P = NP, even if G is bipartite. Furthermore, we present upper bounds for both parameters in the geodetic convexity of bipartite graphs and characterize the families of graphs achieving the bound for the Helly number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 134-141
نویسندگان
, ,