An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
type: Item
instance of: scholarly article
title: An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
zbMATH Open document ID: 0678.68029
DOI: 10.1016/0020-0190(89)90095-1
author: Peter A. Bloniarz
author: S. S. Ravi
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 4112002
zbMATH Keywords: lower bound
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: chain
zbMATH Keywords: algebraic decision trees
zbMATH Keywords: partial order
zbMATH Keywords: fixed order
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90095-1
OpenAlex ID: W1608376243
cites work: Q5338342
cites work: The Ultimate Planar Convex Hull Algorithm?
cites work: Obtaining lower bounds using artificial components
cites work: Q3785970
cites work: A variant of Ben-Or's lower bound for algebraic decision trees
cites work: Decomposing a set of points into chains, with applications to permutation and circle graphs
Recommended article: Decomposing a set of points into chains, with applications to permutation and circle graphs
Recommended article: Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
Recommended article: Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
Recommended article: Lower bounds for approximate polygon decomposition and minimum gap
Recommended article: Lower bounds for randomized algorithms for online chain partitioning
Recommended article: On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
Recommended article: Some optimal algorithms for decomposed partially ordered sets
Recommended article: Q4694722
Recommended article: Partitioning 𝛼–large sets: Some lower bounds
description: scientific article; zbMATH DE number 4112002