First-Fit is Linear on Posets Excluding Two Long Incomparable Chains

Details First-Fit is Linear on Posets Excluding Two Long Incomparable Chains First-Fit is Linear on Posets Excluding Two Long Incomparable Chains

2010-06-29

arxiv.org/abs/1006.5704v3

Order, vol. 28/3, pp. 455--464, 2011

Mathematics

Combinatorics

v3: fixed some typos

Scientific paper

10.1007/s11083-010-9184-y

A poset is (r + s)-free if it does not contain two incomparable chains of
size r and s, respectively. We prove that when r and s are at least 2, the
First-Fit algorithm partitions every (r + s)-free poset P into at most
8(r-1)(s-1)w chains, where w is the width of P. This solves an open problem of
Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992--1999, 2010).

Affiliated with

Also associated with

No associations

Rating

First-Fit is Linear on Posets Excluding Two Long Incomparable Chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with First-Fit is Linear on Posets Excluding Two Long Incomparable Chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First-Fit is Linear on Posets Excluding Two Long Incomparable Chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-315363