Show simple item record

hal.structure.identifierWarwick Mathematics Institute and DIMAP
dc.contributor.authorLozin, Vadim*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorRies, Bernard*
dc.date.accessioned2017-09-05T11:53:45Z
dc.date.available2017-09-05T11:53:45Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16676
dc.descriptionLNCS n°8288en
dc.language.isoenen
dc.subjectIndependent seten
dc.subjectPolynomial-time algorithmen
dc.subjectSubcubic graphen
dc.subject.ddc003en
dc.titleOn the Maximum Independent Set Problem in Subclasses of Subcubic Graphsen
dc.typeCommunication / Conférence
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 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.en
dc.identifier.citationpages314-326en
dc.relation.ispartoftitleCombinatorial Algorithms. 24th International Workshop, IWOCA 2013, Revised Selected Papersen
dc.relation.ispartofeditorLecroq, Thierry
dc.relation.ispartofeditorMouchard, Laurent
dc.relation.ispartofpublnameSpringer Berlin Heidelbergen
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2013
dc.relation.ispartofpages472en
dc.relation.ispartofurl10.1007/978-3-642-45278-9en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-45277-2en
dc.relation.conftitle24th International Workshop, IWOCA 2013en
dc.relation.confdate2013-07
dc.relation.confcityRouenen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-45278-9_27en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-09-05T11:31:26Z
hal.identifierhal-01616215*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record