A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

0.00 Avg rating0 Votes
Article ID: iaor20115257
Volume: 39
Issue: 3
Start Page Number: 213
End Page Number: 217
Publication Date: May 2011
Journal: Operations Research Letters
Authors: , ,
Keywords: cliques
Abstract:

We introduce a family of reductions for removing proper and homogeneous pairs of cliques from a graph G. This family generalizes some routines presented in the literature, mostly in the context of claw‐free graphs. These reductions can be embedded in a simple algorithm that in at most |E(G)‖ steps builds a new graph G′ without proper and homogeneous pairs of cliques, and such that G and G′ agree on the value of some relevant invariant (or property).

Reviews

Required fields are marked *. Your email address will not be published.