An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains

DOI10.1016/0020-0190(89)90095-1zbMath0678.68029OpenAlexW1608376243MaRDI QIDQ1124331

Peter A. Bloniarz, S. S. Ravi

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90095-1

zbMATH Keywords

analysis of algorithmslower boundpartial orderchainalgebraic decision treesfixed order

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (3)

On two-processor scheduling and maximum matching in permutation graphs ⋮ Untangled monotonic chains and adaptive range search ⋮ Fully dynamic algorithms for permutation graph coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• A variant of Ben-Or's lower bound for algebraic decision trees
• Obtaining lower bounds using artificial components
• The Ultimate Planar Convex Hull Algorithm?

This page was built for publication: An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains