Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423843 | Electronic Notes in Discrete Mathematics | 2011 | 7 Pages |
Abstract
Using natural numbers for identifying chains, First-Fit algorithm processes elements of a poset P in some order and for each element it assigns the smallest natural number such that all elements with the same number form a chain.For a class P of posets with bounded-width we prove that there is a constant c such that all posets from P are partitioned by First-Fit into at most c chains if and only if there is a width 2 poset not induced by any poset from P.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
BartÅomiej Bosek, Tomasz Krawczyk, Grzegorz Matecki,