کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419224 | 683753 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Near-linear-time algorithm for the geodetic Radon number of grids
ترجمه فارسی عنوان
الگوریتم نزدیک به زمان خطی برای تعداد رادون نقشه برداری شبکه ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تحدب نمودار؛ تحدب متشکل از سطوح هندسی. تعداد رادون؛ شبکه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The Radon number of a graph is the minimum integer rr such that all sets of at least rr of its vertices can be partitioned into two subsets whose convex hulls intersect. Determining the Radon number of general graphs in the geodetic convexity is NP-hard. In this paper, we show the problem is polynomial for dd-dimensional grids, for all d≥1d≥1. The proposed algorithm runs in near-linear O(d(logd)1/2) time for grids of arbitrary sizes, and in sub-linear O(logd)O(logd) time when all grid dimensions have the same size.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 277–283
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 277–283
نویسندگان
Mitre Costa Dourado, Vinícius Gusmão Pereira de Sá, Dieter Rautenbach, Jayme Luiz Szwarcfiter,