DIMACS TR: 2001-53

Weighted stability in hypergraphs and weighted domination in split graphs

Authors: I. E. Zverovich


We define a family of hereditary subclasses of split graphs where the weighted domination problem is polynomially solvable. Our approach is similar to that of Balas and Yu \cite{BalasY89} for maximal stable sets in graphs.

We apply the result to the subproblem of finding the weighted stability number of a hypergraph.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-53.ps.gz

DIMACS Home Page