کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414317 | 680885 | 2008 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Splitting (complicated) surfaces is hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus g and the number of boundary components b of the surface. Specifically, we describe an algorithm to compute the shortest splitting cycle in (g+b)O(g+b)nlogn time, where n is the complexity of the combinatorial surface.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 41, Issues 1–2, October 2008, Pages 94-110
Journal: Computational Geometry - Volume 41, Issues 1–2, October 2008, Pages 94-110