Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
From MaRDI portal
Publication:2958326
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
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
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