A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
DOI10.1016/J.DISOPT.2006.07.004zbMATH Open1128.68041DBLPjournals/disopt/BlazewiczFKSW07OpenAlexW2162535360WikidataQ57387753 ScholiaQ57387753MaRDI QIDQ2467125FDOQ2467125
Authors: Piotr Formanowicz, Marta Kasprzak, P. Schuurman, Jacek Blazewicz, Gerhard J. Woeginger 
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
Recommendations
- scientific article; zbMATH DE number 1953078
- A DNA algorithm for the maximal matching problem
- Unimodular hypergraph for DNA sequencing: a polynomial time algorithm
- Poisson approximation and dna sequence matching
- Research in Computational Molecular Biology
- An integer programming approach to DNA sequence assembly
Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of DNA sequencing by hybridization.
- Exact arborescences, matchings and cycles
- Matching is as easy as matrix inversion
- Maximum matching of given weight in complete and complete bipartite graphs
- On a linear diophantine problem of Frobenius
- On some properties of DNA graphs
- Optimizing over a slice of the bipartite matching polytope
- The complexity of restricted spanning tree problems
Cited In (6)
This page was built for publication: A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467125)
