کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871791 | 1440191 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Inapproximability results and bounds for the Helly and Radon numbers of a graph
ترجمه فارسی عنوان
نتایج غیر قابل دستیابی و محدوده برای اعداد هلی و رادون یک گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار دو طرفه، محدب جغرافیایی، شماره هلی، غیر قابل پیش بینی بودن تعداد رادون، کران بالا،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 134-141
نویسندگان
Mitre C. Dourado, Aline R. da Silva,