A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs

✍ Scribed by Wen-Lian HSU; George L. Nemhauser

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 688 KB
• Volume: 38
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(82)90169-8

✦ Synopsis

Discrete Mathematics 3X ( 19X2) 6S-71 North-Holland Publishing Company 65 Let G = (V, E) be a graph with a positive number wt(v) assigned to each L' E V. A weighted clique saver of the vertices of G is a collection of cliques with a non-negative weight yC. assigned to each clique C in the collection such that xc. c6c, y,. 3 tit(tl) for all v E V. The problem considered is to mini nizc xc yc-over all weighted c&ue covers. A polynomial time algorithm for this problem is presented for graphs thpt are craw-free and perfect.