Lower Bounds for Selection in X + Y and Other Multisets

DOI10.1145/322092.322097MaRDI QIDQ4170251zbMATH OpenOpenAlexFDO

Authors Donald B. Johnson, Samuel D. Kashdan

Publication date 1978

Published in Journal of the ACM (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cited in

(16)

• Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery
• Complexity of selection in \(X+Y\)
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• On the spanning trees of weighted graphs
• Simple characterizations of \(P(\# P)\) and complete problems
• Optimal algorithms for generalized searching in sorted matrices
• Bi-immunity separates strong NP-completeness notions
• Algorithm 616: fast computation of the Hodges-Lehmann location estimator
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games
• Percentile queries in multi-dimensional Markov decision processes
• The computational complexity of the criticality problems in a network with interval activity times
• On the spanning trees of weighted graphs
• (Multivariate) k-SUM as barrier to succinct computation
• Selection in \(X+Y\) and matrices with sorted rows and columns
• The complexity of the Kth largest subset problem and related problems
• The complexity of searching in \(X+Y\) and other multisets

This page was built for publication: Lower Bounds for Selection in X + Y and Other Multisets

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