The complexity of searching in \(X+Y\) and other multisets

DOI10.1016/0020-0190(90)90144-MzbMath0696.68052MaRDI QIDQ911276

Jean Duprat, Michel Cosnard, Afonso G. Ferreira

Publication date: 1990

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

zbMATH Keywords

complexity of searchingsearching in partial ordered setssorted matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (3)

Optimal algorithms for generalized searching in sorted matrices ⋮ Algorithmic complexity of protein identification: Combinatorics of weighted strings ⋮ On space-efficient algorithms for certain NP-complete problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Complexity of selection in \(X+Y\)
• Generalized Selection and Ranking: Sorted Matrices
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Sorting X + Y
• Computing Partitions with Applications to the Knapsack Problem
• 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

This page was built for publication: The complexity of searching in \(X+Y\) and other multisets