A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants) |
| |
Authors: | Y. Faenza C. Snels |
| |
Affiliation: | a Dipartimento di Matematica Pura e Applicata, Università di Padova, Padua, Italyb Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Rome, Italy |
| |
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). |
| |
Keywords: | Proper and homogeneous pairs of cliques Reductions Graph invariants |
本文献已被 ScienceDirect 等数据库收录! |
|