Independent sets in (P₆, diamond)-free graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2009

Independent sets in (P₆, diamond)-free graphs

Raffaele Mosca
  • Fonction : Auteur
Dipartimento di Scienze - Universita di Chieti-Pescara

Résumé

We prove that on the class of (P6,diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

Domaines

Mathématique discrète [cs.DM]
Fichier principal
Vignette du fichier
509-4151-2-PB.pdf (175.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Service Ist Inria Sophia Antipolis-Méditerranée / I3s  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-00988179

Soumis le : mercredi 7 mai 2014-15:36:40

Dernière modification le : jeudi 29 juin 2023-12:26:04

Archivage à long terme le : jeudi 7 août 2014-11:31:21

Télécharger pour visualiser

Dates et versions

hal-00988179 , version 1 (07-05-2014)

Identifiants

Citer

Raffaele Mosca. Independent sets in (P₆, diamond)-free graphs. Discrete Mathematics and Theoretical Computer Science, 2009, Vol. 11 no. 1 (1), pp.125--140. ⟨10.46298/dmtcs.473⟩. ⟨hal-00988179⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

TDS-MACS
131 Consultations
939 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More