The study of the degree sequences of h-uniform hypergraphs, say h-sequences, was a longstanding open problem in the case of , until very recently where its decision version was proved to be NP-complete. Formally, the decision version of this problem is: Given a non increasing sequence of positive integers, is the degree sequence of a h-uniform simple hypergraph? Now, assuming , we know that such an effective characterization cannot exist even for the case of 3-uniform hypergraphs. However, several necessary or sufficient conditions can be found in the literature; here, relying on a result of S. Behrens et al., we present a sufficient condition for the 3-graphicality of a degree sequence and a polynomial time algorithm that realizes one of the associated 3-uniform hypergraphs, if it exists. Both the results are obtained by borrowing some mathematical tools from discrete tomography, a quite recent research area involving discrete mathematics, discrete geometry and combinatorics.
On the degree sequence of 3-uniform hypergraph: a new sufficient condition / andrea frosini. - STAMPA. - 11414:(2019), pp. 195-205. (Intervento presentato al convegno Discrete Geometry for Computer Imagery, DGCI 2019 tenutosi a fra nel 2019) [10.1007/978-3-030-14085-4_16].
On the degree sequence of 3-uniform hypergraph: a new sufficient condition.
andrea frosini
2019
Abstract
The study of the degree sequences of h-uniform hypergraphs, say h-sequences, was a longstanding open problem in the case of , until very recently where its decision version was proved to be NP-complete. Formally, the decision version of this problem is: Given a non increasing sequence of positive integers, is the degree sequence of a h-uniform simple hypergraph? Now, assuming , we know that such an effective characterization cannot exist even for the case of 3-uniform hypergraphs. However, several necessary or sufficient conditions can be found in the literature; here, relying on a result of S. Behrens et al., we present a sufficient condition for the 3-graphicality of a degree sequence and a polynomial time algorithm that realizes one of the associated 3-uniform hypergraphs, if it exists. Both the results are obtained by borrowing some mathematical tools from discrete tomography, a quite recent research area involving discrete mathematics, discrete geometry and combinatorics.File | Dimensione | Formato | |
---|---|---|---|
LNCS-proof.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
590.66 kB
Formato
Adobe PDF
|
590.66 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.