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

DOI10.1137/090753863zbMath1230.05039MaRDI 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 algorithm; on-line chain partition

Mathematics Subject Classification ID

06A06: Partial orders, general

05A18: Partitions of sets

06A07: Combinatorics of partially ordered sets

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

68W27: Online algorithms; streaming algorithms

05C57: Games on graphs (graph-theoretic aspects)

Related Items

A Dichotomy Theorem for First-Fit Chain Partitions, A subexponential upper bound for the on-line chain partitioning problem, An extremal problem on crossing vectors., First-fit coloring of bounded tolerance graphs, First-Fit is linear on posets excluding two long incomparable chains, On-line chain partitions of orders: a survey, Dimension of posets with planar cover graphs excluding two long incomparable chains, An easy subexponential bound for online chain partitioning, On-line dimension for posets excluding two long incomparable chains, On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains, Unnamed Item, Reverse Mathematics and Grundy colorings of graphs