Journal article

On the maximum independent set problem in subclasses of subcubic graphs

BP2-STS

  • 2014
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
  • English
Classification
Computer science
License
Rights reserved
Open access status
bronze
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/322639
Statistics

Document views: 3 File downloads:
  • independentset.pdf: 9