Selection in \(X+Y\) and matrices with sorted rows and columns

DOI10.1016/0020-0190(85)90123-1zbMath0557.68040OpenAlexW2079849501MaRDI QIDQ761793

D. Kharzeev

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90123-1

zbMATH Keywords

algorithmsortingdivide-and-conquersmallest element

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (10)

An \(O(n^{lg\,k}\cdot 2^{n/2})\) time and \(O(k\cdot 2^{n/k})\) space algorithm for certain NP-complete problems ⋮ River routing in VLSI ⋮ Complexity of selection in \(X+Y\) ⋮ Scheduling with Gaps: New Models and Algorithms ⋮ Optimal algorithms for generalized searching in sorted matrices ⋮ The complexity of searching in \(X+Y\) and other multisets ⋮ On finding connected balanced partitions of trees ⋮ Unnamed Item ⋮ Scheduling with gaps: new models and algorithms ⋮ Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Time bounds for selection
• Generalized Selection and Ranking: Sorted Matrices
• Sorting X + Y
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• Lower Bounds for Selection in X + Y and Other Multisets
• Estimates of Location Based on Rank Tests

This page was built for publication: Selection in \(X+Y\) and matrices with sorted rows and columns