scientific article; zbMATH DE number 2044948

MaRDI QIDQ4448768zbMATH OpenFDO

Authors R. A. Pendavingh, Gerhard J. Woeginger, P. Schuurman

Publication date 18 February 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2204/22040296.htm

zbMATH Keywords

computational complexityDe Bruijn graphDNA computingDNA graphsgraph theoryNP-hardnessrecognition algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Protein sequences, DNA sequences (92D20)

Recommendations

• Recognizing DNA graphs is difficult.
• On the recognition of de Bruijn graphs and their induced subgraphs
• scientific article; zbMATH DE number 2239908
• Characterizations for some types of DNA graphs
• scientific article; zbMATH DE number 1953078

Cited in

(6)

• On the recognition of de Bruijn graphs and their induced subgraphs
• Recognizing DNA graphs is difficult.
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• On the complexity of recognizing Wheeler graphs
• The complexity of approximate pattern matching on de Bruijn graphs
• scientific article; zbMATH DE number 5951415 (Why is no real title available?)

This page was built for publication:

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