On-line dimension for posets excluding two long incomparable chains

DOI10.1007/S11083-011-9222-4MaRDI QIDQ1943697zbMATH OpenOpenAlexFDO

Authors Tomasz Krawczyk, Stefan Felsner, William T. Trotter

Publication date 20 March 2013

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-011-9222-4

zbMATH Keywords

dimensionpartially ordered seton-line algorithmFirst-Fit

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Applications of game theory (91A80) 2-person games (91A05) Combinatorics of partially ordered sets (06A07)

Recommendations

• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• An easy subexponential bound for online chain partitioning
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• On First-Fit coloring of ladder-free posets
• An improved bound for first-fit on posets without two long incomparable chains

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 820116 (Why is no real title available?)
• scientific article; zbMATH DE number 863477 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• A note on first-fit coloring of interval graphs
• A theory of recursive dimension of ordered sets
• An Effective Version of Dilworth's Theorem
• Coloring interval graphs with First-Fit
• Dimension of the crown \(S^k_n\)
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• First-Fit is linear on posets excluding two long incomparable chains
• Intransitive indifference with unequal indifference intervals
• On some packing problem related to dynamic storage allocation
• On-line chain partitions of orders: a survey
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(11)

• scientific article; zbMATH DE number 5762570 (Why is no real title available?)
• First-Fit is linear on posets excluding two long incomparable chains
• On First-Fit coloring of ladder-free posets
• An easy subexponential bound for online chain partitioning
• On-line computations of the ideal lattice of posets
• An extremal problem on crossing vectors.
• An improved bound for first-fit on posets without two long incomparable chains
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• The graph of critical pairs of a crown
• Minors and dimension
• Dimension of posets with planar cover graphs excluding two long incomparable chains

This page was built for publication: On-line dimension for posets excluding two long incomparable chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1943697)