Independent sets in (P₆, diamond)-free graphsArticle
Authors: Raffaele Mosca 1
NULL
Raffaele Mosca
1 Dipartimento di Scienze - Universita di Chieti-Pescara
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.
Peter Gartland;Daniel Lokshtanov;Tomáš Masařík;Marcin Pilipczuk;Michał Pilipczuk;et al., arXiv (Cornell University), Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time, pp. 683-691, 2024, Vancouver BC Canada, 10.1145/3618260.3649791, https://arxiv.org/abs/2305.15738.