Consecutive interval query and dynamic programming on intervals

DOI10.1016/S0166-218X(98)00021-3zbMath0905.90173OpenAlexW2086810418MaRDI QIDQ1392542

Takeshi Tokuyama, Alok Aggarwal

Publication date: 28 July 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

clique coveringinterval queryconsecutive query structurematrix searching in Monge matricessequential partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Cites Work

• A linear-time algorithm for concave one-dimensional dynamic programming
• Applications of generalized matrix searching to geometric algorithms
• Fractional cascading. I: A data structuring technique
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Sequence comparison with mixed convex and concave costs
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• The concave least-weight subsequence problem revisited
• DYNAMIC PROGRAMMING ON INTERVALS
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Matrix searching with the shortest path metric
• Optimal Sequential Partitions of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item