A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
From MaRDI portal
Publication:2467125
DOI10.1016/j.disopt.2006.07.004zbMath1128.68041OpenAlexW2162535360WikidataQ57387753 ScholiaQ57387753MaRDI QIDQ2467125
Piotr Formanowicz, Petra Schuurman, Marta Kasprzak, Gerhard J. Woeginger, Jacek Błażewicz
Publication date: 18 January 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2006.07.004
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Protein sequences, DNA sequences (92D20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact arborescences, matchings and cycles
- Matching is as easy as matrix inversion
- Optimizing over a slice of the bipartite matching polytope
- Complexity of DNA sequencing by hybridization.
- On some properties of DNA graphs
- The complexity of restricted spanning tree problems
- Maximum matching of given weight in complete and complete bipartite graphs
- On a linear diophantine problem of Frobenius