×

Independent sets in (\(P_{6}\),diamond)-free graphs. (English) Zbl 1196.05065

Summary: We prove that on (\(P_{6}\),diamond)-free graphs the Maximum Weight Independent Set problem and the Minimum Weight Independent Dominating Set problem can be solved in polynomial time.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: Link