An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains

DOI10.1137/110855806zbMath1282.06005arXiv1111.2370OpenAlexW3101306282MaRDI QIDQ4899045

David R. Wood, Vida Dujmović, Gwenaël Joret

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.2370

zbMATH Keywords

on-line chain partitionFirst-Fit

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Online algorithms; streaming algorithms (68W27)

Related Items (7)

A subexponential upper bound for the on-line chain partitioning problem ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ An extremal problem on crossing vectors. ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ Dimension of posets with planar cover graphs excluding two long incomparable chains ⋮ An easy subexponential bound for online chain partitioning ⋮ A Dichotomy Theorem for First-Fit Chain Partitions

This page was built for publication: An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains