On intervalizing \(k\)-colored graphs for DNA physical mapping
From MaRDI portal
Publication:5961618
DOI10.1016/S0166-218X(96)00057-1zbMath0867.92008MaRDI QIDQ5961618
Hans L. Bodlaender, Babette de Fluiter
Publication date: 21 April 1997
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
molecular biology; \(O(n^ 2)\) algorithm for biconnected graphs; colored interval graph; sequence reconstruction
68Q25: Analysis of algorithms and problem complexity
05C90: Applications of graph theory
05C38: Paths and cycles
92C40: Biochemistry, molecular biology
92D20: Protein sequences, DNA sequences
05C15: Coloring of graphs and hypergraphs
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of DNA physical mapping
- Beyond NP-completeness for problems of bounded width (extended abstract)
- A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
- Triangulating 3-Colored Graphs
- Triangulating Vertex-Colored Graphs
- The Pathwidth and Treewidth of Cographs
- Triangulating Three-Colored Graphs in Linear Time and Linear Space
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Two strikes against perfect phylogeny
- Mapping the genome
- On intervalizing \(k\)-colored graphs for DNA physical mapping
