On-line adaptive chain covering of upgrowing posets

Tytuł:
On-line adaptive chain covering of upgrowing posets
Czasopismo:
DISCRETE MATHEMATICS & THEORETICAL COMPUTER SCIENCE PROCEEDINGS
Rok:
2006

Opis:
We analyze on-line chain partitioning problem and its variants as a two-person game. One person (Spoiler) builds an on-line poset presenting one point at time. The other one (Algorithm) assigns new point to a chain. Kierstead gave a strategy for Algorithm showing that width w posets can be on-line chain partitioned into 5w−14 chains. Felsner proved that if Spoiler presents an upgrowing poset, i.e., each new point is maximal at the moment of its arrival then there is a strategy for Algorithm usin

Strony:
37-48

Tom (seria wydawnicza):
AF

Link:
http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAF0102

Mathscinet link:
http://www.ams.org/mathscinet-getitem?mr=2508759