On-line chain partitioning problem of on-line posets has been open for the past 20 years. The best known on-line algorithm uses 5~w-1/4 chains to cover poset of width w. Felsner (Theor. Comput. Sci., 175(2):283-292, 1997) introduced a variant of this problem considering only up-growing posets, i.e. on-line posets in which each new point is maximal at the moment of its arrival. He presented an algorithm using (_2~w+1) chains for width w posets and proved that his solution is optimal. In this paper, we study on-line chain partitioning of up-growing interval orders. We prove lower bound and upper bound to be 2w - 1 for width w posets.
展开▼
