An Almost Linear Time Algorithm for Generalized Matrix Searching

DOI10.1137/0403009zbMath0689.68062MaRDI 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 programming; monotone matrix; Ackermann's function; convex quadrangle inequalities

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

90C39: Dynamic programming

52A40: Inequalities and extremum problems involving convexity in convex geometry

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Faster algorithms for largest empty rectangles and boxes, Finding the largest area axis-parallel rectangle in a polygon, 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, Sparse LCS common substring alignment, Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications, Consecutive interval query and dynamic programming on intervals, Guarding in a simple polygon, Approximate regular expression pattern matching with concave gap penalties, Perspectives of Monge properties in optimization, An almost linear time algorithm for field splitting in radiation therapy, Finding least-weight subsequences with fewer processors, Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon, Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search