✦ LIBER ✦

On-line chain partitions of orders

✍ Scribed by Stefan Felsner

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 698 KB
Volume: 175
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(96)00204-6

No coin nor oath required. For personal study only.

✦ Synopsis

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 responds by making an irrevocable assignment of the new point to a chain of a chain partition. Kierstead gave a strategy showing that width k orders can be on-line chain partitioned into (sk -1)/4 chains. We first prove that width two orders can be partitioned on-line into 5 chains. Secondly, we introduce a variant of the game. We impose the restriction that the new point presented by the first player has to be a maximum element in the present order. For this up-growing variant we prove matching upper and lower bounds of ("l') on orders of width k.

📜 SIMILAR VOLUMES

Chain partitions of ordered sets

✍ Willem L. Fouché 📂 Article 📅 1996 🏛 Springer Netherlands 🌐 English ⚖ 651 KB

Problems on chain partitions

✍ Jerrold R. Griggs 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 419 KB

## Problems on chain partitions Recently I have come across several fundamental problems concerning the existence of partitions of posets into chains satisfying certain conditions. Other problems of this sort have been open and frustrating researchers for years. 1 have collected these problems her

Nested Chain Partitions of Hamiltonian F

Nested Chain Partitions of Hamiltonian Filters

✍ David G.C. Horrocks 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 340 KB

Let P be a poset, consisting of all sets X [n]=[1, 2, ..., n] which contain at least one of a given collection F of 2-subsets of [n], ordered by inclusion. By modifying a construction of Greene and Kleitman, we show that if F is hamiltonian, that is, contains [1, 2], [2, 3], ..., [n&1, n] and [1, n]

Chain Partitions of Products of Two Chai

Chain Partitions of Products of Two Chains

✍ Zbigniew Lonc; Muktar E. Elzobi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 167 KB

Measuring and partitioning the high-orde

Measuring and partitioning the high-order linkage disequilibrium by multiple order Markov chains

✍ Yunjung Kim; Sheng Feng; Zhao-Bang Zeng 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 32 KB

the first two authors' equal contribution was not indicated. This erratum corrects the error.

Measuring and partitioning the high-orde

Measuring and partitioning the high-order linkage disequilibrium by multiple order Markov chains

✍ Yunjung Kim; Sheng Feng; Zhao-Bang Zeng 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 663 KB

## Abstract A map of the background levels of disequilibrium between nearby markers can be useful for association mapping studies. In order to assess the background levels of linkage disequilibrium (LD), multilocus LD measures are more advantageous than pairwise LD measures because the combined ana