An Almost Linear Time Algorithm for Generalized Matrix Searching

DOI10.1137/0403009zbMath0689.68062MaRDI QIDQ3031930

Daniel J. Kleitman, Maria M. Klawe

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

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