On-line version of Rabinovitch theorem for proper intervals

Tytuł:
On-line version of Rabinovitch theorem for proper intervals
Czasopismo:
Rok:
2012

Opis:
We analyze the on-line dimension of semi-orders as a two-person game between Algorithm and Spoiler, in a customary way. The game is played in rounds. Spoiler presents a collection of intervals representing a semi-order, one interval at a time. Algorithm maintains its realizer, i.e., the set of linear extensions intersecting the semi-order presented so far. Each time a new interval is presented, Algorithm inserts it into all maintained linear extensions and is not allowed to change the ordering o

Strony:
3426-3436

Tom (seria wydawnicza):
23

Numer DOI:
10.1016/j.disc.2012.02.008

Link:
http://dx.doi.org/10.1016/j.disc.2012.02.008

Web of science link:
http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=7&SID=S1EoCiBlcDDg@H7aNl6&page=1&doc=1

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