ONLINE CHAIN PARTITIONS OF ORDERS

Authors
Citation
S. Felsner, ONLINE CHAIN PARTITIONS OF ORDERS, Theoretical computer science, 175(2), 1997, pp. 283-292
Citations number
4
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
ISSN journal
03043975
Volume
175
Issue
2
Year of publication
1997
Pages
283 - 292
Database
ISI
SICI code
0304-3975(1997)175:2<283:OCPOO>2.0.ZU;2-Y
Abstract
We analyze the on-line chain partitioning problem as a two-person game . One person builds an order one point at a time. The other person res ponds by making an irrevocable assignment of the new point to a chain of a chain partition. Kierstead gave a strategy showing that width k o rders can be on-line chain partitioned into (5(k) - 1)/4 chains. We fi rst prove that width two orders can be partitioned on-line into 5 chai ns. Secondly, we introduce a variant of the game. We impose the restri ction that the new point presented by the first player has to be a max imum element in the present order. For this up-growing variant we prov e matching upper and lower bounds of ((k+1)(2)) on orders of width k.