An Almost Linear Time Algorithm for Generalized Matrix Searching
From MaRDI portal
Publication:3031930
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
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
