First-Fit Algorithm for the On-Line Chain Partitioning Problem

Tytuł:
First-Fit Algorithm for the On-Line Chain Partitioning Problem
Czasopismo:
Rok:
2010

Opis:
We consider a problem of partitioning a partially ordered set into chains by first-fit algorithm. In general this algorithm uses arbitrarily many chains on a class of bounded width posets. In this paper we prove that First-Fit uses at most 3tw(2) chains to partition any poset of width w which does not induce two incomparable chains of height t. In this way we get a wide class of posets with polynomial bound for the on-line chain partitioning problem. We also discuss some consequences of our resu

Strony:
1992-1999

Tom (seria wydawnicza):
23

Numer DOI:
10.1137/090753863

Link:
http://dx.doi.org/10.1137/090753863

Web of science link:
http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=3&SID=S1EoCiBlcDDg@H7aNl6&page=1&doc=1

Mathscinet link:
http://www.ams.org/mathscinet-getitem?mr=2594967