کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427768 686555 2011 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Covering and packing in linear space
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Covering and packing in linear space
چکیده انگلیسی

The fastest known algorithms for the k-cover and the k  -packing problem rely on inclusion–exclusion and fast zeta transform, taking time and space n22n, up to a factor polynomial in the size of the universe n. Here, we introduce a new, fast zeta transform algorithm that improves the space requirement to only linear in the size of the given set family, while not increasing the time requirement. Thus, for instance, the chromatic or domatic number of an n  -vertex graph can be found in time within a polynomial factor of n22n and space O(n1.442)O(1.442n) or O(n1.716)O(1.716n), respectively. For computing the chromatic polynomial, we further reduce the space requirement to O(n1.292)O(1.292n).


► We study the k-cover problem and the k-packing problem.
► We present an algorithm that runs in space linear in the given set family.
► The algorithm is based on a new fast zeta transform.
► We apply to compute the domatic number and chromatic polynomial of a given graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issues 21–22, 15 November 2011, Pages 1033–1036
نویسندگان
, , , ,