Lower bounds for randomized algorithms for online chain partitioning

DOI10.1016/j.ipl.2012.05.010zbMath1248.68548OpenAlexW2056991307MaRDI QIDQ456079

Olga Ohrimenko, Claire Mathieu

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.05.010

zbMATH Keywords

posetrandomized algorithmschain partitiononline chain partitioning

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorics of partially ordered sets (06A07) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• On-line chain partitions of orders
• A decomposition theorem for partially ordered sets
• An Effective Version of Dilworth's Theorem

This page was built for publication: Lower bounds for randomized algorithms for online chain partitioning