Name
Abstract | ||
|---|---|---|
Kobler and Rotics in 2003, and Cameron and Walker in 2005, gave a complete structural description of the graphs G where the matching number ν(G) equals the induced matching number ν2(G). We study their result and use it to analyse graphs G with ν(G)−ν2(G)≤k. We show that the recognition of these graphs can be done in polynomial time for fixed k, and is fixed parameter tractable when parameterized by k for graphs of bounded maximum degree. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.endm.2015.07.003 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
induced matching,strong matching,fixed parameter tractability | Discrete mathematics,Graph,Combinatorics,Parameterized complexity,Indifference graph,Chordal graph,Degree (graph theory),Time complexity,3-dimensional matching,Mathematics,Bounded function | Journal |
Volume | ISSN | Citations |
50 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 7 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Márcio Antônio Duarte | 1 | 0 | 0.68 |
| Felix Joos | 2 | 37 | 11.20 |
| Lucia Draque Penso | 3 | 196 | 20.46 |
| Dieter Rautenbach | 4 | 946 | 138.87 |
| Uéverton S. Souza | 5 | 20 | 21.12 |