A subexponential upper bound for the on-line chain partitioning problem

Tytuł:
A subexponential upper bound for the on-line chain partitioning problem
Czasopismo:
Rok:
2015

Opis:
The main question in the on-line chain partitioning problem is to decide whether there exists an on-line algorithm that partitions posets of width at most w into polynomial number of chains - see Trotter’s chapter Partially ordered sets in the Handbook of Combinatorics. So far the best known on-line algorithm of Kierstead used at most (5^(w −1))/4 chains; on the other hand Szemerédi proved that any on-line algorithm requires at least w+1 over 2 chains. These results were obtained in the early ei

Strony:
1-38

Tom (seria wydawnicza):
35

Numer DOI:
10.1007/s00493-014-2908-7

Link:
http://link.springer.com/article/10.1007%2Fs00493-014-2908-7

Web of science link:
http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=OneClickSearch&qid=5&SID=R1QvhDFEN1BC1bQ4wE7&page=1&doc=1

Mathscinet link:
http://www.ams.org/mathscinet/search/publdoc.html?pg1=INDI&s1=781565&vfpref=html&r=1&mx-pid=3341138