کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414805 | 681046 | 2008 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing a minimum-dilation spanning tree is NP-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In a geometric network G=(S,E), the graph distance between two vertices u,v∈S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation δ>1, it is NP-hard to determine whether a spanning tree of S with dilation at most δ exists.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 41, Issue 3, November 2008, Pages 188-205
Journal: Computational Geometry - Volume 41, Issue 3, November 2008, Pages 188-205