| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313049 |
| ISSN: | 0101-7438 |
| Authors: | Kovalev, Michel1 Maurras, Jean-Francois2 Vaxes, Yann |
| Institutions: | 1Belarusian State University, Belarus Faculty of Applied Mathematics and Informatics, Minsk. Bielorrusia 2Universite de Marseille, Laboratoire d'Informatique Fondamentale de Marseille, Marseille, Bouches-du-Rhone. Francia |
| Year: | 2003 |
| Season: | Ene-Abr |
| Volumen: | 23 |
| Number: | 1 |
| Pages: | 99-109 |
| Country: | Brasil |
| Language: | Inglés |
| Document type: | Artículo |
| Approach: | Experimental |
| English abstract | Let Kn be the complete undirected graph with n vertices. A 3-cycle is a cycle consisting of 3 edges. The 3-cycle polytope is defined as the convex hull of the incidence vectors of all 3-cycles in Kn. In this paper, we present a polyhedral analysis of the 3-cycle polytope. In particular, we give several classes of facet defining inequalities of this polytope and we prove that the separation problem associated to one of these classes of inequalities is NP-complete. Finally, it is proved that the 3-cycle polytope is a 2-neighborly polytope |
| Disciplines: | Matemáticas |
| Keyword: | Matemáticas aplicadas, Cápsulas convexas, Politopos, Ciclos, Grafos completos |
| Keyword: | Mathematics, Applied mathematics, Convex hulls, Polytopes, Cycles, Complete graphs |
| Full text: | Texto completo (Ver HTML) |
