کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418560 | 681688 | 2015 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the recognition of unit disk graphs and the Distance Geometry Problem with Ranges
ترجمه فارسی عنوان
در شناخت نمودارهای دیسک واحد و مشکل هندسه دور با محدوده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار دیسک واحد هندسه دور گسسته سازی، تریگراف
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We introduce a method to decide whether a graph GG admits a realization on the plane in which two vertices lie within unitary distance from one another exactly if they are neighbors in GG. Such graphs are called unit disk graphs, and their recognition is a known NP-hard problem. By iteratively discretizing the plane, we build a sequence of geometrically defined trigraphs–graphs with mandatory, forbidden and optional adjacencies–until either we find a realization of GG or the interruption of such a sequence certifies that no realization exists. Additionally, we consider the proposed method in the scope of the more general Distance Geometry Problem with Ranges, where arbitrary intervals of pairwise distances are allowed.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 197, 31 December 2015, Pages 3–19
Journal: Discrete Applied Mathematics - Volume 197, 31 December 2015, Pages 3–19
نویسندگان
Guilherme Dias da Fonseca, Vinícius Gusmão Pereira de Sá, Raphael Carlos Santos Machado, Celina Miraglia Herrera de Figueiredo,