کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419747 | 683856 | 2009 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The parameterized complexity of the induced matching problem The parameterized complexity of the induced matching problem](/preview/png/419747.png)
Given a graph GG and an integer k≥0k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset MM of size at least kk such that MM is a matching and no two edges of MM are joined by an edge of GG. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is WW[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 715–727