Computing the all-pairs longest chains in the plane

DOI10.1007/3-540-57155-8_229zbMATH Open1504.68247OpenAlexW1583932855MaRDI QIDQ5060093FDOQ5060093

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)