Domination, independent domination, and duality in strongly chordal graphs (Q788002)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Domination, independent domination, and duality in strongly chordal graphs
scientific article

    Statements

    Domination, independent domination, and duality in strongly chordal graphs (English)
    0 references
    0 references
    1984
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    minimum weight dominating sets
    0 references
    independent dominating sets
    0 references
    strongly chordal graphs
    0 references
    totally balanced matrices
    0 references
    0 references
    0 references