A Note on Chernikova's algorithm

Hervé Le Verge 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : This paper describes an implementation of Chernikova's algorithm for finding an irredundant set of vertices for a given polyhedron defined by a set of linear inequalities and equations. This algorithm can also be used for the dual problem : given a set of extremal rays and vertices, find the associated irredundant set of facet supporting hyperplanes. The method is an extension of initial Chernikova's algorithm (non negative domain) and is mainly based on the polyhedral cone duality principle. A new en hancement for extremal ray detection is presented together with its effects on a class of polyedra.
Type de document :
Rapport
[Research Report] RR-1662, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074895
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:49:33
Dernière modification le : vendredi 16 novembre 2018 - 01:30:17
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:57:40

Fichiers

Identifiants

  • HAL Id : inria-00074895, version 1

Citation

Hervé Le Verge. A Note on Chernikova's algorithm. [Research Report] RR-1662, INRIA. 1992. 〈inria-00074895〉

Partager

Métriques

Consultations de la notice

438

Téléchargements de fichiers

337