Parameterized complexity of two-interval pattern problem

DOI10.1016/J.TCS.2021.12.005MaRDI QIDQ2067621zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Saeed Mehrabi, Debajyoti Mondal

Publication date 18 January 2022

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

Full work available at URL https://arxiv.org/abs/2002.05099

zbMATH Keywords

interval graphsparameterized complexitytwo-interval pattern

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Parameterized complexity of two-interval pattern problem
• Combinatorial Pattern Matching
• On two open problems of 2-interval patterns
• Algorithms and Computation
• Improved algorithms for largest cardinality 2-interval pattern problem

Cites work

• scientific article; zbMATH DE number 2087043 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• 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
• Approximating the 2-interval pattern problem
• Combinatorial Pattern Matching
• Extracting constrained 2-interval subsets in 2-interval sets
• Improved algorithms for largest cardinality 2-interval pattern problem
• On the Approximability of Comparing Genomes with Duplicates
• On the computational complexity of 2-interval pattern matching problems
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On two open problems of 2-interval patterns
• Scheduling Split Intervals

Cited in

(4)

• Algorithms – ESA 2005
• A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem
• Parameterized complexity of two-interval pattern problem
• On the computational complexity of 2-interval pattern matching problems

Describes a project that uses

Uses Software

• HotKnots

This page was built for publication: Parameterized complexity of two-interval pattern problem

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