Name
Abstract | ||
|---|---|---|
Extending results of Kobler and Rotics (2003), Cameron and Walker (2005) gave a complete structural description of the graphs G where the matching number ¿ ( G ) equals the induced matching number ¿ 2 ( G ) . We present a short proof of their result and use it to study 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.tcs.2015.04.001 | Theoretical Computer Science |
Keywords | Field | DocType |
Induced matching,Strong matching,Fixed parameter tractability | Discrete mathematics,Graph,Parameterized complexity,Combinatorics,Degree (graph theory),Time complexity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
588 | C | 0304-3975 |
Citations | PageRank | References |
3 | 0.39 | 6 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Márcio Antônio Duarte | 1 | 3 | 0.39 |
| 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 |