Packing r-Cliques in Weighted Chordal Graphs |
| |
Authors: | P. Hell S. Klein L. T. Nogueira F. Protti |
| |
Affiliation: | (1) School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada, V5A 1S6;(2) IM and COPPE/Sistemas, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, CEP 21945-970, Rio de Janeiro, RJ, Brazil;(3) COPPE/Sistemas, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, CEP, 21945-970 Rio de Janeiro, RJ, Brazil;(4) IM and NCE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, CEP, 20001-970 Rio de Janeiro, RJ, Brazil |
| |
Abstract: | In 1, we have previously observed that, in a chordal graph G, the maximum number of independent r-cliques (i.e., of vertex disjoint subgraphs of G, each isomorphic to Kr, with no edges joining any two of the subgraphs) equals the minimum number of cliques of G that meet all the r-cliques of G. When r = 1, this says that chordal graphs have independence number equal to the clique covering number. When r = 2, this is equivalent to a result of Cameron (1989), and it implies a well known forbidden subgraph characterization of split graphs. In this paper we consider a weighted version of the above min-max optimization problem. Given a chordal graph G, with a nonnegative weight for each r-clique in G, we seek a set of independent r-cliques with maximum total weight. We present two algorithms to solve this problem, based on the principle of complementary slackness. The first one operates on a graph derived from G, and is an adaptation of an algorithm of Farber (1982). The second one improves the performance by reducing the number of constraints of the linear programs. Both results produce a min-max relation. When the algorithms are specialized to the situation in which all the r-cliques have the same weight, we simplify the algorithms reported in 1, although these simpler algorithms are not as efficient. As a byproduct, we also obtain new elementary proofs of the above min-max result. |
| |
Keywords: | chordal graphs min-max theorems greedy algorithms linear programming duality complementary slackness |
本文献已被 SpringerLink 等数据库收录! |
|