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
Piotr Formanowicz, P. Schuurman, Gerhard J. Woeginger, Marta Kasprzak, Jacek Blazewicz
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?)
- On some properties of DNA graphs
- Title not available (Why is that?)
- Maximum matching of given weight in complete and complete bipartite graphs
- Title not available (Why is that?)
- Matching is as easy as matrix inversion
- Complexity of DNA sequencing by hybridization.
- The complexity of restricted spanning tree problems
- Exact arborescences, matchings and cycles
- Optimizing over a slice of the bipartite matching polytope
- On a linear diophantine problem of Frobenius
Cited In (4)
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)
