Groupe d’études et de recherche en analyse des décisions

G-92-18

Two Algorithms for Maximum Cliques in Dense Graphs

et

It is shown that any vertex which is simplicial in the complementary graph of a given graph belongs to at least one maximum clique of that graph. This property is exploited in two algorithms. The first one is a variation on the recent algorithm of Carraghan and Pardalos, checking only for leaves in the complementary graph. The second one detects systematically simplicial vertices within small cliques. Computational experience is reported and is very favorable for dense graphs.

, 16 pages