An Almost Linear Time Algorithm for Generalized Matrix Searching

DOI10.1137/0403009zbMath0689.68062OpenAlexW2016871180MaRDI QIDQ3031930

Maria M. Klawe, Daniel J. Kleitman

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingmonotone matrixAckermann's functionconvex quadrangle inequalities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Dynamic programming (90C39) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Related Items

Finding least-weight subsequences with fewer processors ⋮ Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications ⋮ Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ Perspectives of Monge properties in optimization ⋮ Consecutive interval query and dynamic programming on intervals ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ An almost linear time algorithm for field splitting in radiation therapy ⋮ Unnamed Item ⋮ Applications of generalized matrix searching to geometric algorithms ⋮ An optimal algorithm with unknown time complexity for convex matrix searching ⋮ Minimum \(L_k\) path partitioning-an illustration of the Monge property ⋮ Finding the largest area axis-parallel rectangle in a polygon ⋮ Unnamed Item ⋮ Sparse LCS common substring alignment ⋮ Unnamed Item ⋮ Guarding in a simple polygon