Domination, independent domination, and duality in strongly chordal graphs (Q788002): Difference between revisions

Polynomial-time algorithms for finding minimum weight dominating sets and independent dominating sets in strongly chordal graphs are presented in this paper. The algorithms are based on linear programming formulations of the problems and consist of two stages: in the first - a greedy algorithm is used to solve the corresponding dual program, and in the second - feasible solution to the primal is read off. In the second part, a relationship between strongly chordal graphs and totally balanced matrices is utilized to show that the domatic number achieves its theoretical lower bound in strongly chordal graphs and to efficiently solve certain optimization problems for totally balanced matrices.