کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655988 | 685250 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the Complexity of Finding Paths in a Two-Dimensional Domain II: Piecewise Straight-Line Paths
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The problem of finding a piecewise straight-line path, with a constant number of line segments, in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. It is proved that, for polynomial-time recognizable domains associated with polynomial-time computable distance functions, the complexity of this problem is equivalent to a discrete problem which is complete for â2P, the second level of the polynomial-time hierarchy.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 120, 3 February 2005, Pages 45-57
Journal: Electronic Notes in Theoretical Computer Science - Volume 120, 3 February 2005, Pages 45-57
نویسندگان
Arthur W. Chou, Ker-I Ko,