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

Font Size:  Small  Medium  Large

Independent sets in (P6,diamond)-free graphs

Raffaele Mosca


We prove that on (P6,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