Skip to Main content Skip to Navigation

The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs

Valentin Bouquet 1, 2 Christophe Picouleau 1
1 CEDRIC - OC - CEDRIC. Optimisation Combinatoire
CEDRIC - Centre d'études et de recherche en informatique et communications
2 CEDRIC - ROC - CEDRIC. Réseaux et Objets Connectés
CEDRIC - Centre d'études et de recherche en informatique et communications
Abstract : We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02448239
Contributor : Christophe Picouleau <>
Submitted on : Tuesday, February 11, 2020 - 5:17:37 PM
Last modification on : Friday, February 14, 2020 - 3:57:31 PM

File

2001.07554.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02448239, version 1
  • ARXIV : 2001.07554

Collections

Citation

Valentin Bouquet, Christophe Picouleau. The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs. 2020. ⟨hal-02448239⟩

Share

Metrics

Record views

53

Files downloads

3