Advertisement
Published in:
2011 | OriginalPaper | Chapter
Parameterized Algorithms for Inclusion of Linear Matchings
Author : Sylvain Guillemot
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A
linear matching
consists of 2
n
vertices ordered linearly, together with
n
vertex-disjoint edges. In this article, we study the
Linear Matching Inclusion
problem, which takes two linear matchings, called the
pattern
and the
target
, and asks if there is an order-preserving mapping of the pattern into the target. We consider several parameterizations of this problem, for which we obtain parameterized algorithms and hardness results. In addition, we settle the parameterized complexity of the related
Nesting-Free 2-Interval Pattern
problem.