| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313049 |
| ISSN: | 0101-7438 |
| Autores: | Kovalev, Michel1 Maurras, Jean-Francois2 Vaxes, Yann |
| Instituciones: | 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 |
| Año: | 2003 |
| Periodo: | Ene-Abr |
| Volumen: | 23 |
| Número: | 1 |
| Paginación: | 99-109 |
| País: | Brasil |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Experimental |
| Resumen en inglés | 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 |
| Disciplinas: | Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Cápsulas convexas, Politopos, Ciclos, Grafos completos |
| Keyword: | Mathematics, Applied mathematics, Convex hulls, Polytopes, Cycles, Complete graphs |
| Texto completo: | Texto completo (Ver HTML) |
