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

2-intervalcombinatorial approximation algorithmsRNA secondary structure prediction

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

• 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
• 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?)
• 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

(14)

• On recovering syntenic blocks from comparative maps
• On the computational complexity of 2-interval pattern matching problems
• Parameterized complexity of two-interval pattern problem
• Recognizing d-interval graphs and d-track interval graphs
• Extracting constrained 2-interval subsets in 2-interval sets
• 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?)
• Algorithms – ESA 2005
• Algorithms and Computation
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Generalizing Roberts' characterization of unit interval graphs
• Complexity issues in color-preserving graph embeddings
• A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem
• Improved algorithms for largest cardinality 2-interval pattern problem

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)