Domination, independent domination, and duality in strongly chordal graphs.

*(English)*Zbl 0531.05045Polynomial-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.

Reviewer: M.M.Sysło

##### MSC:

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

90C10 | Integer programming |

##### Keywords:

minimum weight dominating sets; independent dominating sets; strongly chordal graphs; totally balanced matrices
Full Text:
DOI

##### References:

[1] | R.P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms, to appear. |

[2] | Berge, C., Balanced matrices, Math. programming, 2, 19-31, (1972) · Zbl 0247.05126 |

[3] | Beyer, T.; Proskurowski, A.; Hedetniemi, S.; Michell, S., Independent domination in trees, (), 321-328 |

[4] | Booth, K.S.; Johnson, J.H., Dominating sets in chordal graphs, SIAM J. comput., 11, 191-199, (1982) · Zbl 0485.05055 |

[5] | G.J. Chang, Private communication, 1982. |

[6] | Chang, G.J.; Nemhauser, G.L., The k-domination and k-stability problems on graphs, () · Zbl 0576.05054 |

[7] | Cockayne, E.; Goodman, S.; Hedetniemi, S., A linear algorithm for the domination number of a tree, Inform. process. letters, 4, 41-44, (1975) · Zbl 0311.68024 |

[8] | Cockayne, E.J.; Hedetniemi, S.T., Towards a theory of domination in graphs, Networks, 7, 247-261, (1977) · Zbl 0384.05051 |

[9] | Farber, M., Domination and duality in weighted trees, () · Zbl 0498.05025 |

[10] | Farber, M.; Farber, M., Applications of 1.p. duality to problems involving independence and domination, (), also issued as · JFM 56.0042.02 |

[11] | Farber, M., Independent domination in chordal graphs, Operations research letters, 1, 134-138, (1982) · Zbl 0495.05053 |

[12] | Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048 |

[13] | Fulkerson, D.R.; Hoffman, A.J.; Oppenheim, R., On balanced matrices, Math. programming study, 1, 120-132, (1974) · Zbl 0357.90038 |

[14] | Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039 |

[15] | A.J. Hoffman, A.W.J. Kolen and M. Sakarovitch, Totally-balanced and greedy matrices, submitted to SIAM J. Algebraic Discrete Methods. · Zbl 0573.05041 |

[16] | Khachian, L.G., A polynomial algorithm in linear programming, Soviet math. dokl., 20, 191-194, (1979) · Zbl 0409.90079 |

[17] | Lovász, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001 |

[18] | Lubiw, A., Λ-free matrices, () |

[19] | Natarajan, K.S.; White, L.J., Optimum domination in weighted trees, Inform. process. letters, 7, 261-265, (1978) · Zbl 0391.05046 |

[20] | Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602 |

[21] | Rose, D.J.; Tarjan, R.E.; Lueker, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019 |

[22] | Simmons, D.M., Linear programming for operations research, (1972), Holden-Day San Francisco, CA · Zbl 0234.90028 |

[23] | Slater, P.J., R-domination in graphs, J. assoc. comput. Mach., 23, 446-450, (1976) · Zbl 0349.05120 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.