An easy subexponential bound for online chain partitioning
From MaRDI portal
Publication:1753118
zbMath1390.06001arXiv1410.3247MaRDI QIDQ1753118
Tomasz Krawczyk, Grzegorz Matecki, Bartłomiej Bosek, Matthew E. Smith, Henry A. Kierstead
Publication date: 25 May 2018
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.3247
Combinatorics of partially ordered sets (06A07) Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)
Related Items (3)
Improved lower bound on the on-line chain partitioning of semi-orders with representation ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ A Dichotomy Theorem for First-Fit Chain Partitions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A subexponential upper bound for the on-line chain partitioning problem
- First-fit coloring on interval graphs has performance ratio at least 5
- 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
- A note on first-fit coloring of interval graphs
- A polynomial time approximation algorithm for dynamic storage allocation
- On-line chain partitions of orders
- Coloring interval graphs with First-Fit
- Intransitive indifference with unequal indifference intervals
- A decomposition theorem for partially ordered sets
- First-Fit Algorithm for the On-Line Chain Partitioning Problem
- The Linearity of First-Fit Coloring of Interval Graphs
- An Effective Version of Dilworth's Theorem
- On-Line Coloring and Recursive Graph Theory
- 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: An easy subexponential bound for online chain partitioning
