On-line chain partitions of orders: a survey

DOI10.1007/s11083-011-9197-1zbMath1259.06002OpenAlexW2151140709WikidataQ72990570 ScholiaQ72990570MaRDI QIDQ766153

Tomasz Krawczyk, Kamil Kloch, Bartłomiej Bosek, Stefan Felsner, Grzegorz Matecki, Piotr Micek

Publication date: 23 March 2012

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11083-011-9197-1

zbMATH Keywords

survey paperpartially ordered setsonline-chain partitioning

Mathematics Subject Classification ID

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

Related Items (13)

A subexponential upper bound for the on-line chain partitioning problem ⋮ On-line dimension of semi-orders ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Improved lower bound on the on-line chain partitioning of semi-orders with representation ⋮ Improved lower bounds on the on-line chain partitioning of posets of bounded dimension ⋮ On-line dimension for posets excluding two long incomparable chains ⋮ On-line chain partitions of up-growing semi-orders ⋮ 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 ⋮ Deferred on-line bipartite matching ⋮ An easy subexponential bound for online chain partitioning ⋮ Unnamed Item ⋮ Online coloring a token graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on first-fit coloring of interval graphs
• On-line chain partitions of orders
• Coloring interval graphs with First-Fit
• On-line chain partitions of up-growing semi-orders
• Efficient dependency tracking for relevant events in concurrent systems
• A theory of recursive dimension of ordered sets
• On-line chain partitioning of up-growing interval orders
• Intransitive indifference with unequal indifference intervals
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• Foundational aspects of theories of measurement
• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• On-Line Coloring and Recursive Graph Theory
• Optimal on-line coloring of circular arc graphs
• Automata, Languages and Programming
• Partially Ordered Sets

This page was built for publication: On-line chain partitions of orders: a survey