کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414541 | 680974 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
ترجمه فارسی عنوان
درختان پوشای ژئودزی صفحه، چرخه های همیلتون و هماهنگی کامل در یک چندضلعی ساده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای جغرافیایی؛ نمودارهای غیرمتقاطع؛ درختان پوشا ؛ چرخه هامیلتونی؛ تطابق کامل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let S be a finite set of points in the interior of a simple polygon P. A geodesic graph , GP(S,E)GP(S,E), is a graph with vertex set S and edge set E such that each edge (a,b)∈E(a,b)∈E is the shortest geodesic path between a and b inside P . GPGP is said to be plane if the edges in E do not cross. If the points in S are colored, then GPGP is said to be properly colored provided that, for each edge (a,b)∈E(a,b)∈E, a and b have different colors. In this paper we consider the problem of computing (properly colored) plane geodesic perfect matchings, Hamiltonian cycles, and spanning trees of maximum degree three.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 57, August 2016, Pages 27–39
Journal: Computational Geometry - Volume 57, August 2016, Pages 27–39
نویسندگان
Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid,