An Optimal Algorithm for the Maximum-Density Segment Problem

DOI10.1137/S0097539704440430zbMath1087.68120OpenAlexW3099635146MaRDI QIDQ4651540

Kai-Min Chung, Hsueh-I Lu

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539704440430

zbMATH Keywords

bioinformaticscomputational geometryslope selectiondata structurebiological sequence analysismaximum-density segmentsequence algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Protein sequences, DNA sequences (92D20) Data structures (68P05) Computational methods for problems pertaining to biology (92-08)

Related Items (17)

Finding a maximum-density path in a tree under the weight and length constraints ⋮ On the range maximum-sum segment query problem ⋮ Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics ⋮ The density maximization problem in graphs ⋮ Programming from Galois connections ⋮ Cache oblivious algorithms for the RMQ and the RMSQ problems ⋮ Calculating a linear-time solution to the densest-segment problem ⋮ Finding long and similar parts of trajectories ⋮ Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths ⋮ Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence ⋮ An improved algorithm for finding a length-constrained maximum-density subtree in a tree ⋮ An optimal algorithm for the maximum-density path in a tree ⋮ Algorithms for Problems on Maximum Density Segment ⋮ On locating disjoint segments with maximum sum of densities ⋮ Fast algorithms for the density finding problem ⋮ AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING ⋮ Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint

This page was built for publication: An Optimal Algorithm for the Maximum-Density Segment Problem