Show simple item record

dc.contributor.authorRies, Bernard*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorLozin, Vadim*
dc.date.accessioned2014-09-26T07:59:41Z
dc.date.available2014-09-26T07:59:41Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13963
dc.language.isoenen
dc.subjectAPX-completenessen
dc.subjectSubcubic graphen
dc.subjectPolynomial-time algorithmen
dc.subjectIndependent seten
dc.subject.ddc003en
dc.titleOn the maximum independent set problem in subclasses of subcubic graphsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDIMAP and Mathematics Institute, University of Warwick, Coventry;Royaume-Uni
dc.description.abstractenIt 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 classen
dc.relation.isversionofjnlnameJournal of Discrete Algorithms
dc.relation.isversionofjnlvol31
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages104-112
dc.relation.isversionofdoi10.1016/j.jda.2014.08.005en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds107888*
hal.identifierhal-01508780*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record