کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414755 681025 2011 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum vertex cover in rectangle graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Minimum vertex cover in rectangle graphs
چکیده انگلیسی

We consider the Minimum Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families R where R1∖R2 is connected for every pair of rectangles R1,R2∈R. This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of (1.5+ε) in general rectangle families, for any fixed ε>0, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles in a novel way.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 44, Issues 6–7, August 2011, Pages 356-364