First-Fit Algorithm for the On-Line Chain Partitioning Problem

DOI10.1137/090753863zbMath1230.05039OpenAlexW2042443761MaRDI QIDQ3058541

Edward Szczypka, Bartłomiej Bosek, Tomasz Krawczyk

Publication date: 3 December 2010

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

Full work available at URL: https://doi.org/10.1137/090753863

zbMATH Keywords

First-Fit algorithmon-line chain partition

Mathematics Subject Classification ID

Partial orders, general (06A06) Partitions of sets (05A18) Combinatorics of partially ordered sets (06A07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (12)

A subexponential upper bound for the on-line chain partitioning problem ⋮ On-line dimension for posets excluding two long incomparable chains ⋮ An extremal problem on crossing vectors. ⋮ 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 ⋮ Dimension of posets with planar cover graphs excluding two long incomparable chains ⋮ An easy subexponential bound for online chain partitioning ⋮ First-fit coloring of bounded tolerance graphs ⋮ Unnamed Item ⋮ Reverse Mathematics and Grundy colorings of graphs ⋮ A Dichotomy Theorem for First-Fit Chain Partitions ⋮ On-line chain partitions of orders: a survey

This page was built for publication: First-Fit Algorithm for the On-Line Chain Partitioning Problem