On-line chain partitions of orders: a survey
DOI10.1007/S11083-011-9197-1zbMATH Open1259.06002DBLPjournals/order/BosekFKKMM12OpenAlexW2151140709WikidataQ72990570 ScholiaQ72990570MaRDI QIDQ766153FDOQ766153
Authors: Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, 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
Recommendations
Online algorithms; streaming algorithms (68W27) Combinatorics in computer science (68R05) Applications of game theory (91A80) 2-person games (91A05) Combinatorics of partially ordered sets (06A07)
Cites Work
- Title not available (Why is that?)
- On-line chain partitions of orders
- On-line chain partitions of up-growing semi-orders
- A theory of recursive dimension of ordered sets
- On-line chain partitioning of up-growing interval orders
- Intransitive indifference with unequal indifference intervals
- On-line chain partitioning as a model for real-time scheduling
- First-Fit Algorithm for the On-Line Chain Partitioning Problem
- Foundational aspects of theories of measurement
- On some packing problem related to dynamic storage allocation
- An Effective Version of Dilworth's Theorem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Coloring interval graphs with First-Fit
- The Linearity of First-Fit Coloring of Interval Graphs
- Title not available (Why is that?)
- Partially Ordered Sets
- On-line and first fit colorings of graphs
- On-Line Coloring and Recursive Graph Theory
- Title not available (Why is that?)
- Automata, Languages and Programming
- A note on first-fit coloring of interval graphs
- Efficient dependency tracking for relevant events in concurrent systems
- Optimal on-line coloring of circular arc graphs
Cited In (18)
- Title not available (Why is that?)
- A subexponential upper bound for the on-line chain partitioning problem
- First-Fit is linear on posets excluding two long incomparable chains
- Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
- Improved lower bound on the on-line chain partitioning of semi-orders with representation
- An easy subexponential bound for online chain partitioning
- On-line chain partitions of up-growing semi-orders
- On-line dimension of semi-orders
- On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
- Online dimension of partially ordered sets
- On-line chain partitioning of up-growing interval orders
- A linear-time parameterized algorithm for computing the width of a DAG
- Variants of online chain partition problem of posets
- On-line chain partitioning as a model for real-time scheduling
- Deferred on-line bipartite matching
- Online coloring a token graph
- Forbidden structures for efficient first-fit chain partitioning (extended abstract)
- On-line dimension for posets excluding two long incomparable chains
This page was built for publication: On-line chain partitions of orders: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q766153)
