Lower bounds for the matrix chain ordering problem

DOI10.1007/3-540-59175-3_85zbMath1495.68092OpenAlexW1516171582MaRDI QIDQ5096328

Gregory J. E. Rawlins, Phillip G. Bradford, Venkatesh Choppella

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_85

zbMATH Keywords

optimal triangulationassociative productvertex weightlinear productmatrix dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Computation of Matrix Chain Products. Part II
• An O(n) algorithm to find a near-optimum partition of a convex polygon
• Computation of Matrix Chain Products. Part I
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• An O(n) algorithm for determining a near-optimal computation order of matrix chain products
• A New Lower Bound Technique and Its Application: Tight Lower Bound for a Polygon Triangulation Problem
• An optimal parallel algorithm for computing a near-optimal order of matrix multiplications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item