Approximating maximum weight K-colorable subgraphs in chordal graphs
We present a 2-approximation algorithm for the problem of finding the maximum weight K-colorable subgraph in a given chordal graph with node weights. The running time of the algorithm is O(K(n + m)), where n and m are the number of vertices and edges in the given graph. (C) 2008 Elsevier B.V. All rights reserved.
chordal graphs approximation algorithms coloring interval graphs