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

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