Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Entire DC Network
The On-Line Width Of Various Classes Of Posets., Israel R. Curbelo
The On-Line Width Of Various Classes Of Posets., Israel R. Curbelo
Electronic Theses and Dissertations
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemer\'edi proved that any on-line algorithm could be forced to use $\binom{w+1}{2}$ chains to partition a poset of width $w$. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In the survey paper by Bosek et al., variants of the problem were studied where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size $d$. We prove …