On-line adaptive chain covering of upgrowing posets

Tytuł:

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):

Link:

https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAF0102.html

Mathscinet link:

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

Access:

OTWARTY

Licencja:

Creative Commons - Uznanie Autorstwa (CC-BY)

Wersja tekstu:

Ostateczna wersja opublikowana

Sposób udostępinienia:

Otwarte czasopismo

Data udostępnienia publikacji:

W momencie opublikowania