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

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). © 2011 Elsevier B.V. All rights reserved.


Published in:
Operations Research Letters, 39, 3, 213-217
Year:
2011
ISSN:
01676377
Keywords:
Laboratories:




 Record created 2012-10-25, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)