Determining DNA sequence similarity using maximum independent set algorithms for interval graphs

DOI10.1007/3-540-55706-7_29zbMath1502.92009OpenAlexW1852889450MaRDI QIDQ5056152

João Meidanis, Deborah Joseph, Prasoon Tiwari

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55706-7_29

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (14)

Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ The disruptive anti-covering location problem ⋮ Solving the anti-covering location problem using Lagrangian relaxation ⋮ On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Temporal interval cliques and independent sets ⋮ Three ways to cover a graph ⋮ Efficient chaining of seeds in ordered trees ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ Lagrangean relaxation with clusters for point-feature cartographic label placement problems ⋮ Recognizing Proper Tree-Graphs ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On \(H\)-topological intersection graphs ⋮ Facets for node packing ⋮ The Local Queue Number of Graphs with Bounded Treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal sequence alignment allowing for long gaps
• Interval graphs and maps of DNA
• Sequence comparison with concave weighting functions
• On double and multiple interval graphs
• Total Domination and Irredundance in Weighted Interval Graphs
• Efficient algorithms for interval graphs and circular-arc graphs

This page was built for publication: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs