A New Facet Generating Procedure for the Stable Set Polytope
| Autor: | Álinson S. Xavier, Manoel B. Campêlo |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
medicine.medical_specialty Facet (geometry) Birkhoff polytope Applied Mathematics Polyhedral combinatorics Polytope Uniform k 21 polytope Combinatorics Independent set Convex polytope medicine Mathematics::Metric Geometry Discrete Mathematics and Combinatorics Vertex enumeration problem Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 37:183-188 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2011.05.032 |
| Popis: | We introduce a new facet-generating procedure for the stable set polytope, based on replacing ( k − 1 )-cliques with certain k-partite graphs, which subsumes previous procedures based on replacing vertices with stars, and thus also many others in the literature. It can be used to generate new classes of facet-defining inequalities. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect