Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
From MaRDI portal
Publication:5056152
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
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
