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

Autor:	Faenza, Yuri, Oriolo, Gianpaolo, Snels, Claudia
Rok vydání:	2011
Předmět:	Mathematics - Optimization and Control Computer Science - Discrete Mathematics Mathematics - Combinatorics 05C85 68R10
Druh dokumentu:	Working Paper
Popis:	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). Comment: 8 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1103.2601 Zobrazit plný text záznamu View this record from Arxiv