Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication

DOI10.1016/S1571-0661(04)00313-5zbMath1268.65062WikidataQ59443004 ScholiaQ59443004MaRDI QIDQ2841268

Tadao Takaoka

Publication date: 24 July 2013

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

The 2D subarray polytope ⋮ Efficient algorithms for the maximum sum problems ⋮ Average-case complexity of the min-sum matrix product problem ⋮ A compositional framework for developing parallel programs on two-dimensional arrays ⋮ Unnamed Item

Cites Work

• A new upper bound on the complexity of the all pairs shortest path problem
• On the exponent of all pairs shortest path problem
• Subcubic cost algorithms for the all pairs shortest path problem
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Unnamed Item
• Unnamed Item