کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
423602 685262 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cyclic Extensions of Order Varieties
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Cyclic Extensions of Order Varieties
چکیده انگلیسی

We study complexity problems involving three sorts of combinational structures: cyclic orders, order varieties and cycles. It is known that the problem of telling whether a cyclic order is included in some cycle is NP-complete. We show that the same question for order varieties, a special class of cyclic orders, is in L. For this, we relate the entropy relation between partial orders to the forcing relation of graph theory.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 212, 30 April 2008, Pages 119-132