A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem

DOI10.1007/S10878-006-9024-6MaRDI QIDQ996823zbMATH OpenOpenAlexFDO

Authors Minghui Jiang

Publication date 19 July 2007

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-9024-6

zbMATH Keywords

RNA secondary structure predictionApproximation algorithms2-Interval

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)

Recommendations

• Approximating the 2-interval pattern problem
• Algorithms – ESA 2005
• A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model
• Combinatorial Pattern Matching
• On the computational complexity of 2-interval pattern matching problems
• Parameterized complexity of two-interval pattern problem
• Parameterized complexity of two-interval pattern problem
• On two open problems of 2-interval patterns
• scientific article; zbMATH DE number 2087043
• Improved algorithms for largest cardinality 2-interval pattern problem

Cites work

• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• Algorithms and Computation
• Algorithms – ESA 2005
• Combinatorial Pattern Matching
• On the computational complexity of 2-interval pattern matching problems
• Trapezoid graphs and generalizations, geometry and algorithms

Cited in

(9)

• Improved algorithms for largest cardinality 2-interval pattern problem
• A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model
• On Recovering Syntenic Blocks from Comparative Maps
• Parameterized complexity of two-interval pattern problem
• On recovering syntenic blocks from comparative maps
• Algorithms and Computation
• Combinatorial Pattern Matching
• Algorithms – ESA 2005
• Approximating the 2-interval pattern problem

This page was built for publication: A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem

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