Minimum Weighted Coloring of Triangulated Graphs, with Application to Weighted Vertex Packing in Arbitrary Graphs.

摘要

Efficient algorithms are known for finding a maximum weight stable set, a minimum weight clique covering, and a maximum-weight clique of a vertex-weighted triangulated graph. However, there is no comparably efficient algorithm in the literature for finding a minimum weighted vertex coloring of such a graph. We give an O(V squared) procedure for this problem (Algorithm 1). We then extend the procedure to the problem of finding in an arbitrary graph G = (V,E) a maximal induced subgraph G(W) color-equivalent (as defined in Section 3) to a maximal triangulated subgraph G(T). (Algorithm 2). Finally, we use this latter algorithm as the main ingredient of a branch and bound procedure for the maximum weight clique problem in an arbitrary graph. We present computational experience on arbitrary random graphs with up to 1000 vertices.