Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound

DOI10.1007/978-3-319-48749-6_24zbMath1483.68143OpenAlexW2545219809MaRDI QIDQ2958326

Sung Eun Bae, Tong-Wook Shinn, Tadao Takaoka

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
• An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• A new upper bound on the complexity of the all pairs shortest path problem
• On the exponent of all pairs shortest path problem
• Improved algorithm for all pairs shortest paths
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Minimal Triangulations of Polygonal Domains
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• P-COMPLETE GEOMETRIC PROBLEMS

This page was built for publication: Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound