Date/heure
Date(s) - 13/10/2022
14 h 00 - 16 h 00
Emplacement
Amphithéâtre Georges Friedmann
Catégories
Voici les diapositives du séminaire talk_2022_Parigi
Le prochain séminaire du Cédric aura lieu le13 octobre 2022, à 14h, dans l’amphithéâtre Georges Friedmann, proposé par l’axe « Science des données ». Nous aurons le plaisir d’écouter Andrea Frosini de l’Université de Florence, et Valentine Huré, doctorante dans l’équipe OC.
Premier exposé: Andrea Frosini, Université de Florence,
Reconstruction problems on uniform hypergraphs
The problem of characterizing degree sequences of graphs has been of great interest for the scientific community since 1960 when Erdosh and Gallai first proved that it can be solved in polynomial time. Later several algorithms has been defined for their reconstruction. Moving to hypergraphs, these same problems are more challenging also concerning the simple class of 3-uniform ones. Some examples of P-time reconstructable classes are provided. The general reconstruction problem remained open till 2019 when Deza et al. found the proof of its NP-hardness. So, it become of main interest to restrict the computationally hard core of the problem. Here, a class of hypergraphs introduced by Deza et al. is defined and some properties together with euristics for its reconstruction are shown. FInally, an interesting problem related to hypergraph reconstruction, say null label problem, is proposed together with some preliminary results.