Name
Abstract | ||
|---|---|---|
It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for 3-regular Hamiltonian graphs and for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of H is a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time. We also strengthen the NP-completeness of the problem on 3-regular Hamiltonian graphs by showing that the problem is APX-complete in this class. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jda.2014.08.005 | Journal of Discrete Algorithms |
Keywords | DocType | Volume |
Independent set,Polynomial-time algorithm,Subcubic graph,APX-completeness | Conference | 31 |
Issue | ISSN | Citations |
C | 1570-8667 | 6 |
PageRank | References | Authors |
0.45 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vadim V. Lozin | 1 | 947 | 83.65 |
| Jérôme Monnot | 2 | 512 | 55.74 |
| Bernard Ries | 3 | 176 | 28.68 |