On the maximum independent set problem in subclasses of subcubic graphs
BP2STS
Published in:
 Journal of Discrete Algorithms.  Elsevier BV.  2014, vol. 31, p. 104112
English
It is known that the maximum independent set problem is NPcomplete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NPcomplete for 3regular Hamiltonian graphs and for Hfree 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 His a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for Hfree subcubic graphs in polynomial time. We also strengthen the NPcompleteness of the problem on 3regular Hamiltonian graphs by showing that the problem is APXcomplete in this class.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science

License

Rights reserved

Open access status

bronze

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/322639
Statistics
Document views: 4
File downloads: