A Linear Time Algorithm for the k Maximal Sums Problem

DOI10.1007/978-3-540-74456-6_40MaRDI QIDQ3525591zbMATH OpenOpenAlexWikidataFDO

Authors Gerth Stølting Brodal, Allan Grønlund Jørgensen

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_40

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Recommendations

• Algorithms and Computation
• Improved algorithms for the \(k\) maximum-sums problems
• Algorithms and Computation
• Efficient algorithms for \(k\) maximum sums
• Computing and Combinatorics

Cited in

(16)

• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence
• scientific article; zbMATH DE number 4123286 (Why is no real title available?)
• A provably fast linear-expected-time maxima-finding algorithm
• Algorithms and Computation
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Efficient algorithms for the maximum sum problems
• Algorithm for K Disjoint Maximum Subarrays
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
• Algorithms and Computation
• Selecting Sums in Arrays
• Efficient algorithms for \(k\) maximum sums
• Improved algorithms for the \(k\) maximum-sums problems
• Minimizing the sum of the \(k\) largest functions in linear time.
• A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem
• Optimal algorithms for the average-constrained maximum-sum segment problem

This page was built for publication: A Linear Time Algorithm for the k Maximal Sums Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3525591)