On-line Chain Partitioning of Up-growing Interval Orders

Tytuł:
On-line Chain Partitioning of Up-growing Interval Orders
Czasopismo:
Rok:
2007

Opis:
On-line chain partitioning problem of on-line posets has been open for the past 20 years. The best known on-line algorithm uses 5w-1/4 chains to cover poset of width w. Felsner (Theor. Comput. Sci., 175( 2): 283 - 292, 1997) introduced a variant of this problem considering only up-growing posets, i.e. on-line posets in which each new point is maximal at the moment of its arrival. He presented an algorithm using ((w+ 1)2) chains for width w posets and proved that his solution is optimal. In this

Strony:
1-13

Tom (seria wydawnicza):
24

Numer DOI:
10.1007/s11083-006-9050-0

Link:
http://dx.doi.org/10.1007/s11083-006-9050-0

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

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