کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9655859 685323 2005 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Variants of Online Chain Partition Problem of Posets
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Variants of Online Chain Partition Problem of Posets
چکیده انگلیسی
Online chain partitioning problem of posets is open for at least last 15 years. The best known online algorithm uses 5w−14 chains to cover width w posets. A variant of this problem considering only upgrowing posets, i.e. online posets in which every, new point is maximal at the moment it arrives, has been solved by Felsner [S. Felsner On-line chain partitions of orders, Theoretical Computer Science 175 (1997) 283-292]. He presented an algorithm using (w+12) chains to cover posets of width w. Moreover, he proved that this is an optimal solution. We are interested in special class of posets, namely the interval posets. For this class we present an algorithm using 2w−1 chains for width w and we prove that there is no better algorithm. In [S. Felsner On-line chain partitions of orders, Theoretical Computer Science 175 (1997) 283-292] Felsner also considers an adaptive chain covering problem for upgrowing posets. We are able to show a lowerbound for this problem to be (2−ɛ)⋅w for width w posets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 140, 18 November 2005, Pages 3-13
نویسندگان
, ,