Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search

DOI10.1007/978-3-662-47672-7_47zbMath1440.68049arXiv1502.07663OpenAlexW2963318061WikidataQ60143014 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Special matrices (15B99)

Related Items (4)

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Unnamed Item ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item

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

This page was built for publication: Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search