An Optimal Algorithm for the Maximum Two-Chain Problem

DOI10.1137/0405022MaRDI QIDQ4012450zbMATH OpenOpenAlexFDO

Authors

Publication date 27 September 1992

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dominance hulllower boundmax two-chainpoint dominance

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• An Optimal Algorithm for the Maximum Three-Chain Problem
• Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
• Maxima-finding algorithms for multidimensional samples: A two-phase approach
• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains

Cited in

(12)

• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Maximum \(k\)-covering of weighted transitive graphs with applications
• Circular permutation graph family with applications
• Single step searching in weighted block graphs
• A discrete and continuous study of the \textsc{Max-Chain-Formation} problem
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• An Optimal Algorithm for the Maximum Three-Chain Problem
• Algorithms for two bottleneck optimization problems
• scientific article; zbMATH DE number 1226311 (Why is no real title available?)
• Maximum weightk-independent set problem on permutation graphs
• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
• scientific article; zbMATH DE number 894762 (Why is no real title available?)

This page was built for publication: An Optimal Algorithm for the Maximum Two-Chain Problem

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