Optimal algorithms for generalized searching in sorted matrices

DOI10.1016/S0304-3975(97)00027-3zbMATH Open0894.68040MaRDI QIDQ1389660FDOQ1389660

Authors: Hong Shen 

Publication date: 30 June 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• On parallel selection and searching in partial orders: Sorted matrices
• Optimal parallel selection in sorted matrices
• Parallel searching in generalized Monge arrays
• Parallel multiple search

zbMATH Keywords

time complexityoptimal algorithmCRCW PRAMprocessorswork-optimalmatrix search problemsorted matrix

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Cites Work

• Estimates of Location Based on Rank Tests
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Generalized Selection and Ranking: Sorted Matrices
• Title not available (Why is that?)
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Lower Bounds for Selection in X + Y and Other Multisets
• On parallel selection and searching in partial orders: Sorted matrices
• Optimal parallel selection in sorted matrices
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Complexity of selection in \(X+Y\)
• The complexity of searching in \(X+Y\) and other multisets

Cited In (6)

• Parallel multiple search
• An optimal algorithm with unknown time complexity for convex matrix searching
• Title not available (Why is that?)
• The complexity of searching in \(X+Y\) and other multisets
• Title not available (Why is that?)
• A faster parallel algorithm for a matrix searching problem

This page was built for publication: Optimal algorithms for generalized searching in sorted matrices

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