On the complexity of non-unique probe selection

DOI10.1016/J.TCS.2007.10.014MaRDI QIDQ2474080zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1945182 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• The complexity of facets resolved

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

Describes a project that uses

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)