On-line chain partitions of orders: a survey
From MaRDI portal
Publication:766153
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
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
