Approximating the 2-interval pattern problem

DOI10.1016/J.TCS.2008.01.007MaRDI QIDQ932323zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Maxime Crochemore, Danny Hermelin, Gad M. Landau, Dror Rawitz, 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 prediction2-intervalcombinatorial approximation algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• Algorithms – ESA 2005
• A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem
• A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model
• Improved algorithms for largest cardinality 2-interval pattern problem
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 1954383 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• A unified approach to approximating resource allocation and scheduling
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Combinatorial Pattern Matching
• Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
• Extremal Values of the Interval Number of a Graph
• On double and multiple interval graphs
• One for the price of two: a unified approach for approximating covering problems
• Topics in Intersection Graph Theory
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring

Cited in

(13)

• On the computational complexity of 2-interval pattern matching problems
• Extracting constrained 2-interval subsets in 2-interval sets
• A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem
• Improved algorithms for largest cardinality 2-interval pattern problem
• A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model
• scientific article; zbMATH DE number 2087043 (Why is no real title available?)
• Parameterized complexity of two-interval pattern problem
• On recovering syntenic blocks from comparative maps
• Algorithms and Computation
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Complexity issues in color-preserving graph embeddings
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Algorithms – ESA 2005

This page was built for publication: Approximating the 2-interval pattern problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q932323)