On-line and off-line vertex enumeration by adjacency lists
| Autor: | Pierre Hansen, Pey-Chun Chen, Brigitte Jaumard |
|---|---|
| Rok vydání: | 1991 |
| Předmět: |
Mathematics::Combinatorics
Applied Mathematics Algebraic enumeration MathematicsofComputing_NUMERICALANALYSIS Neighbourhood (graph theory) Polytope Management Science and Operations Research Industrial and Manufacturing Engineering Graph enumeration Vertex (geometry) Combinatorics Polyhedron TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Mathematics::Metric Geometry Adjacency list Vertex enumeration problem Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Operations Research Letters. 10:403-409 |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/0167-6377(91)90042-n |
| Popis: | We propose a new algorithm to solve the on-line vertex enumeration problem for polytopes, doing all computations in n-space, where n is the dimension of the polytope. This algorithm exploits adjacency lists between vertices and uses no simplex tableaux. It can handle the cases of empty or degenerate polyhedra. A theoretical and numerical comparison with existing approaches for off-line vertex enumeration is presented. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|