Computation of Dominating Partitions
E. J. Cockayne, F. D. K. Roberts · INFOR Information Systems and Operational Research · 1977
Let P,Q be the independent sets of vertices which define a bipartite graph. An algorithm is presented for determining the largest order partition of P into sets which dominate Q. Specialization of the procedure enables us to compute largest dominating partitions of graphs, directed graphs and systems of sets. The method is enumerative and is based upon the branch and bound technique of integer programming. Several applications are mentioned, and computational experience with the technique is discussed.