On the maximum independent set problem in subclasses of subcubic graphs
BP2-STS
Published in:
- Journal of Discrete Algorithms. - Elsevier BV. - 2014, vol. 31, p. 104-112
English
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 His 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.
-
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: