On the enumeration of the set of numerical semigroups with fixed Frobenius number
| Autor: | Víctor Blanco, José Carlos Rosales |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Kunz-coordinates vectors Genus Polytope Congruence relation Numerical semigroup Computational Mathematics Computational Theory and Mathematics Homogeneous Partitions of sets Modelling and Simulation Modeling and Simulation Enumeration Special classes of semigroups Partition (number theory) Frobenius number Integer programming Algorithms Mathematics |
| Zdroj: | Computers & Mathematics with Applications. 63:1204-1211 |
| ISSN: | 0898-1221 |
| DOI: | 10.1016/j.camwa.2011.12.034 |
| Popis: | In this paper, we present an efficient algorithm to compute the whole set of numerical semigroups with a given Frobenius number F. The methodology is based on the construction of a partition of that set by a congruence relation. It is proven that each class in the partition contains exactly one irreducible and one homogeneous numerical semigroup, and from those two elements the whole class can be reconstructed. An alternative encoding of a numerical semigroup, its Kunz-coordinates vector, is used to propose a simple methodology to enumerate the desired set by manipulating a lattice polytope of 0–1 vectors and solving certain integer programming problems over it. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect