Article ID Journal Published Year Pages File Type
6423843 Electronic Notes in Discrete Mathematics 2011 7 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,