On intervalizing \(k\)-colored graphs for DNA physical mapping

DOI10.1016/S0166-218X(96)00057-1zbMath0867.92008OpenAlexW2006714678MaRDI QIDQ5961618

Babette de Fluiter, Hans L. Bodlaender

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

zbMATH Keywords

molecular biology\(O(n^ 2)\) algorithm for biconnected graphscolored interval graphsequence reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Paths and cycles (05C38) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Coloring of graphs and hypergraphs (05C15)

Related Items (15)

The Turing way to parameterized complexity ⋮ Improved Lower Bounds for Graph Embedding Problems ⋮ Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems ⋮ Characterizing width two for variants of treewidth ⋮ A short note on the complexity of computing strong pathbreadth ⋮ Unit interval editing is fixed-parameter tractable ⋮ Complexity classification of some edge modification problems ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ NP-completeness results for edge modification problems ⋮ Completing colored graphs to meet a target property ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ Unnamed Item ⋮ Exact algorithms for intervalizing coloured graphs

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

This page was built for publication: On intervalizing \(k\)-colored graphs for DNA physical mapping