An (n log n) lower bound for decomposing a set of points into chains
From MaRDI portal
Publication:1124331
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
Cites work
- scientific article; zbMATH DE number 4049081 (Why is no real title available?)
- scientific article; zbMATH DE number 3211107 (Why is no real title available?)
- A variant of Ben-Or's lower bound for algebraic decision trees
- Decomposing a set of points into chains, with applications to permutation and circle graphs
- Obtaining lower bounds using artificial components
- The Ultimate Planar Convex Hull Algorithm?
Cited in
(7)- An Optimal Algorithm for the Maximum Two-Chain Problem
- Fully dynamic algorithms for permutation graph coloring
- Untangled monotonic chains and adaptive range search
- On a universal chain problem
- Decomposing a set of points into chains, with applications to permutation and circle graphs
- 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)
