Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search

DOI10.1145/3381416MaRDI QIDQ4987433zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Shay Mozes, Oren Weimann

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3381416

zbMATH Keywords

Monge matrixpredecessor searchrange queries

Mathematics Subject Classification ID

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

Recommendations

• Submatrix maximum queries in Monge matrices are equivalent to predecessor search
• Improved submatrix maximum queries in Monge matrices
• Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Superlinear bounds for matrix searching problems

Cited in

(7)

• Faster connectivity in low-rank hypergraphs via expander decomposition
• Submatrix maximum queries in Monge matrices are equivalent to predecessor search
• Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications
• Improved submatrix maximum queries in Monge matrices
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Finding a small vertex cut on distributed networks
• Approximate circular pattern matching

This page was built for publication: Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987433)