Approximating the 2-interval pattern problem

DOI10.1016/j.tcs.2008.01.007zbMath1142.68070OpenAlexW2091929603WikidataQ61677919 ScholiaQ61677919MaRDI QIDQ932323

Gad M. Landau, Maxime Crochemore, Dror Rawitz, Stéphane Vialette, Danny Hermelin

Publication date: 10 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-00619979/file/2-Interval.pdf

zbMATH Keywords

RNA secondary structure prediction2-intervalcombinatorial approximation algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items

Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ Complexity issues in color-preserving graph embeddings ⋮ On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ Parameterized complexity of two-interval pattern problem ⋮ On recovering syntenic blocks from comparative maps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
• One for the price of two: a unified approach for approximating covering problems
• On double and multiple interval graphs
• Extremal Values of the Interval Number of a Graph
• Topics in Intersection Graph Theory
• Combinatorial Pattern Matching
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A unified approach to approximating resource allocation and scheduling