Improved lower bound on the on-line chain partitioning of semi-orders with representation

DOI10.1016/j.disc.2023.113656zbMath1522.68759arXiv2111.04790MaRDI QIDQ6056742

Csaba Biró, Israel R. Curbelo

Publication date: 4 October 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.04790

zbMATH Keywords

bandwidthsemiorderonline algorithmchain partitioning

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• A subexponential upper bound for the on-line chain partitioning problem
• On-line chain partitions of orders: a survey
• A new lower bound for the on-line coloring of intervals with bandwidth
• An easy subexponential bound for online chain partitioning
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• On some packing problem related to dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• Automata, Languages and Programming
• Approximation and Online Algorithms

This page was built for publication: Improved lower bound on the on-line chain partitioning of semi-orders with representation