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

DOI10.1007/s00493-014-2908-7zbMath1349.68324OpenAlexW2083080918MaRDI QIDQ276436

Bartłomiej Bosek, Tomasz Krawczyk

Publication date: 3 May 2016

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-014-2908-7

zbMATH Keywords

partially ordered setonline algorithmchain partitioning

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Online algorithms; streaming algorithms (68W27) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (4)

Improved lower bound on the on-line chain partitioning of semi-orders with representation ⋮ First-Fit is linear on posets excluding two long incomparable chains ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ An easy subexponential bound for online chain partitioning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-Fit is linear on posets excluding two long incomparable chains
• On First-Fit coloring of ladder-free posets
• On-line chain partitions of orders: a survey
• On-line chain partitions of orders
• On-line chain partitions of up-growing semi-orders
• A theory of recursive dimension of ordered sets
• On-line chain partitioning of up-growing interval orders
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• On some packing problem related to dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
• First-Fit Coloring of Incomparability Graphs

This page was built for publication: A subexponential upper bound for the on-line chain partitioning problem