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

Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

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

Raffaele Mosca

Abstract

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

Full Text: PDF Untitled PostScript

Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

Independent sets in (P6,diamond)-free graphs

Abstract

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