کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430866 | 688218 | 2013 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum weight Euclidean t-spanner is NP-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a set P of points in the plane, an Euclidean t-spanner for P is a geometric graph that preserves the Euclidean distances between every pair of points in P up to a constant factor t. The weight of a geometric graph refers to the total length of its edges. In this paper we show that the problem of deciding whether there exists an Euclidean t-spanner, for a given set of points in the plane, of weight at most w is NP-hard for every real constant t>1t>1, both whether planarity of the t-spanner is required or not.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 22, September 2013, Pages 30–42
Journal: Journal of Discrete Algorithms - Volume 22, September 2013, Pages 30–42
نویسندگان
Paz Carmi, Lilach Chaitman-Yerushalmi,