Computing the all-pairs longest chains in the plane

DOI10.1007/3-540-57155-8_229MaRDI QIDQ5060093zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, Mikhail J. Atallah

Publication date 18 January 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57155-8_229

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10)

Recommendations

• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
• Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
• Computing maximal chains
• Algorithms for longest chains in pseudo-transitive graphs
• A simple algorithm for enumerating longest distances in the plane
• Computing optimal 2-3 chains for pairings
• Computing Maximally Separated Sets in the Plane
• Planar graph decomposition and all pairs shortest paths
• Algorithms for computing lengths of chains in integral partition lattices.
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs

Cites work

• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms on circular-arc graphs
• An Efficient Parallel Biconnectivity Algorithm
• Efficient algorithms for interval graphs and circular-arc graphs
• Efficient Parallel Algorithms for String Editing and Related Problems
• Finding maximum cliques in circle graphs
• scientific article; zbMATH DE number 432842 (Why is no real title available?)
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• New clique and independent set algorithms for circle graphs
• On computing the length of longest increasing subsequences
• Parallel rectilinear shortest paths with rectangular obstacles
• Permutation Graphs and Transitive Graphs
• Some beautiful arguments using mathematical induction
• Some modified algorithms for Dijkstra's longest upsequence problem
• The Parallel Evaluation of General Arithmetic Expressions
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(3)

• An Optimal Algorithm for the Maximum Three-Chain Problem
• Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE

This page was built for publication: Computing the all-pairs longest chains in the plane

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