کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433829 | 689635 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Matchings in higher-order Gabriel graphs
ترجمه فارسی عنوان
تطبیق در گرافهای بالاتر از گابریل؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار گابریل، نمودارهای بالاتر از گابریل، تطابق
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a set P of n points in the plane, the order-k Gabriel graph on P , denoted by k-GGk-GG, has an edge between two points p and q if and only if the closed disk with diameter pq contains at most k points of P, excluding p and q . We study matching problems in k-GGk-GG graphs. We show that a Euclidean bottleneck matching of P is contained in 10-GG10-GG, but 8-GG8-GG may not have any Euclidean bottleneck matching. In addition we show that 0-GG0-GG has a matching of size at least n−14 and this bound is tight. We also prove that 1-GG1-GG has a matching of size at least 2(n−1)5 and 2-GG2-GG has a perfect matching. Finally we consider the problem of blocking the edges of k-GGk-GG.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 596, 6 September 2015, Pages 67–78
Journal: Theoretical Computer Science - Volume 596, 6 September 2015, Pages 67–78
نویسندگان
Ahmad Biniaz, Anil Maheshwari, Michiel Smid,