An (n log n) lower bound for decomposing a set of points into chains
From MaRDI portal
Publication:1124331
DOI10.1016/0020-0190(89)90095-1zbMATH Open0678.68029OpenAlexW1608376243MaRDI QIDQ1124331FDOQ1124331
Authors: 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
Recommendations
- Decomposing a set of points into chains, with applications to permutation and circle graphs
- Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
- Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
- Lower bounds for approximate polygon decomposition and minimum gap
- Lower bounds for randomized algorithms for online chain partitioning
- On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
- Some optimal algorithms for decomposed partially ordered sets
- scientific article; zbMATH DE number 219236
- Partitioning 𝛼–large sets: Some lower bounds
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Cites Work
- The Ultimate Planar Convex Hull Algorithm?
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (7)
- Untangled monotonic chains and adaptive range search
- Decomposing a set of points into chains, with applications to permutation and circle graphs
- An Optimal Algorithm for the Maximum Two-Chain Problem
- Fully dynamic algorithms for permutation graph coloring
- On a universal chain problem
- On two-processor scheduling and maximum matching in permutation graphs
- An Optimal Algorithm for the Maximum Three-Chain Problem
This page was built for publication: An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124331)
