A subexponential upper bound for the on-line chain partitioning problem
From MaRDI portal
Publication:276436
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
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
