Approximating the 2-interval pattern problem

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

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

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 prediction; 2-interval; combinatorial approximation algorithms

Mathematics Subject Classification ID

68W20: Randomized algorithms

Related Items

On the parameterized complexity of some optimization problems related to multiple-interval graphs, Complexity issues in color-preserving graph embeddings, On recovering syntenic blocks from comparative maps, Extracting constrained 2-interval subsets in 2-interval sets

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