Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms

DOI10.1137/S0097539794266171MaRDI QIDQ4210143zbMATH OpenFDO

Authors Stefan Felsner, Lorenz Wernisch

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539794266171

zbMATH Keywords

algorithmsantichainschainsorderspoint setsskeletonsYoung tableaux

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics of partially ordered sets (06A07) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• k-Sets of Convex Inclusion Chains of Planar Point Sets
• On maximum area polygons in a planar point set
• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
• Computing the all-pairs longest chains in the plane
• An algorithmic approach to maximal unions of chains in a partially ordered set
• Maximum planar sets that determine k distances
• Extremal polygonal chains on k-matchings
• Planar point sets with large minimum convex decompositions
• An algorithm for maximum common subgraph of planar triangulation graphs
• The Maximum Independent Set Problem in Planar Graphs

Cited in

(15)

• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Interlacing and scaling exponents for the geodesic watermelon in last passage percolation
• Longest increasing subsequences in windows based on canonical antichain partition
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• A discrete and continuous study of the \textsc{Max-Chain-Formation} problem
• An Optimal Algorithm for the Maximum Three-Chain Problem
• An Optimal Algorithm for the Maximum Two-Chain Problem
• Anomaly Detection and Classification for Streaming Data using PDEs
• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
• scientific article; zbMATH DE number 905031 (Why is no real title available?)
• Computing the all-pairs longest chains in the plane
• On the Erdős-Szekeres problem for convex permutations and orthogonally convex point sets
• Fast RSK correspondence by doubling search
• Forbidden patterns in mixed linear layouts

This page was built for publication: Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210143)