کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414922 681103 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Independent set of intersection graphs of convex objects in 2D
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Independent set of intersection graphs of convex objects in 2D
چکیده انگلیسی

The intersection graph of a set of geometric objects is defined as a graph G=(S,E) in which there is an edge between two nodes si, sj∈S if si∩sj≠∅. The problem of computing a maximum independent set in the intersection graph of a set of objects is known to be NP-complete for most cases in two and higher dimensions. We present approximation algorithms for computing a maximum independent set of intersection graphs of convex objects in R2. Specifically, given (i) a set of n line segments in the plane with maximum independent set of size α, we present algorithms that find an independent set of size at least (α/(2log(2n/α)))1/2 in time O(n3) and (α/(2log(2n/α)))1/4 in time O(n4/3logcn), (ii) a set of n convex objects with maximum independent set of size α, we present an algorithm that finds an independent set of size at least (α/(2log(2n/α)))1/3 in time O(n3+τ(S)), assuming that S can be preprocessed in time τ(S) to answer certain primitive operations on these convex sets, and (iii) a set of n rectangles with maximum independent set of size βn, for β⩽1, we present an algorithm that computes an independent set of size Ω(β2n). All our algorithms use the notion of partial orders that exploit the geometric structure of the convex objects.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 34, Issue 2, May 2006, Pages 83-95