Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
From MaRDI portal
Publication:3448817
DOI10.1007/978-3-662-47672-7_47zbMath1440.68049arXiv1502.07663WikidataQ60143014 ScholiaQ60143014MaRDI QIDQ3448817
Paweł Gawrychowski, Oren Weimann, Shay Mozes
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.07663
Related Items
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On Cartesian trees and range minimum queries
- Orthogonal range searching in linear and almost-linear space
- Geometric applications of a matrix-searching algorithm
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Perspectives of Monge properties in optimization
- Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima
- Two Dimensional Range Minimum Queries and Fibonacci Lattices
- Time-space trade-offs for predecessor search
- An Almost Linear Time Algorithm for Generalized Matrix Searching
- Two-Dimensional Range Minimum Queries
- On Space Efficient Two Dimensional Range Minimum Data Structures
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Improved Submatrix Maximum Queries in Monge Matrices
- Orthogonal range searching on the RAM, revisited
