A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem

DOI10.1007/978-3-540-77120-3_65zbMath1155.68601MaRDI QIDQ5387809

Tadao Takaoka, Sung Eun Bae

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_65

Mathematics Subject Classification ID

68W40: Analysis of algorithms

Related Items

Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence

Cites Work

• Unnamed Item
• Ranking \(k\) maximum sums
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• A new upper bound on the complexity of the all pairs shortest path problem
• Improved algorithm for all pairs shortest paths
• A Linear Time Algorithm for the k Maximal Sums Problem
• Algorithm for K Disjoint Maximum Subarrays
• More algorithms for all-pairs shortest paths in weighted graphs
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• Computing and Combinatorics
• Algorithms and Data Structures
• An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
• Algorithms and Computation
• Computing and Combinatorics
• Algorithms and Computation
• Algorithms and Computation