کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421368 684206 2008 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of monotone dualization and generating minimal hypergraph transversals
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the complexity of monotone dualization and generating minimal hypergraph transversals
چکیده انگلیسی

In 1994 Fredman and Khachiyan established the remarkable result that the duality of a pair of monotone Boolean functions, in disjunctive normal forms, can be tested in quasi-polynomial time, thus putting the problem, most likely, somewhere between polynomiality and coNP-completeness. We strengthen this result by showing that the duality testing problem can in fact be solved in polylogarithmic time using a quasi-polynomial number of processors (in the PRAM model). While our decomposition technique can be thought of as a generalization of that of Fredman and Khachiyan, it yields stronger bounds on the sequential complexity of the problem in the case when the sizes of f and g are significantly different, and also allows for generating all minimal transversals of a given hypergraph using only polynomial space.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 11, 6 June 2008, Pages 2109–2123
نویسندگان
,