First-Fit Algorithm for the On-Line Chain Partitioning Problem
From MaRDI portal
Publication:3058541
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
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