On the complexity of non-unique probe selection

DOI10.1016/J.TCS.2007.10.014zbMATH Open1134.68025OpenAlexW2063037290MaRDI QIDQ2474080FDOQ2474080

Authors: Yongxi Cheng, Weili Wu, Ker-I Ko 

Publication date: 5 March 2008

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.10.014

Recommendations

• On the complexity and approximation of non-unique probe selection using \(d\)-disjunct matrix
• Integer linear programming approaches for non-unique probe selection
• Non-unique probe selection and group testing
• On dynamic bit-probe complexity
• Automata, Languages and Programming
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Algorithmic Learning Theory
• On the complexity of working set selection

zbMATH Keywords

separable matrices\(\Sigma _2^{\text{P}}\)-completeDP-completenon-unique probe selection

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• The complexity of facets resolved
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• DP-Complete Problems Derived from Extremal NP-Complete Properties
• Integer linear programming approaches for non-unique probe selection
• In Memoriam: Ker-I Ko (1950–2018)
• On the complexity and approximation of non-unique probe selection using \(d\)-disjunct matrix
• Non-unique probe selection and group testing

Uses Software

• OligoPicker

This page was built for publication: On the complexity of non-unique probe selection

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