Internships (équipe Combinatoire, LIX, Ecole Polytechnique)

Internships 2019-20 ("stages de recherche")


Past internship students (M1/M2)


Gabriel Beauplet (2019): Tétraèdres en Diamants : Structure de Données Compacte pour Maillages Tétraèdriques

Gaspard Denis (2017): Fast spherical drawing of planar triangulations
(published in the Proc. of 17th Int. Symposium on Experimental Algorithms (SEA 2018), LIPIcs, vol. 103, p. 24:1-24:14, 2018, link).
Martin Jocqueviel (2016): Plongement d'un graphe triangulaire sur le tore (co-advisor: Maks Ovsjanikov)

Kevin Bienvenu (2015): Using a spectral multi-scaled aging method to visualize and analyze dynamic networks (co-advisor: Maks Ovsjanikov)

David Uribe (2015): Drawing triangulations with a prescribed inner face in linear time and polynomial resolution.

Alexandre Nolin (2014): Efficient and practical tree preconditioning for solving Laplacian systems (co-advisor: Maks Ovsjanikov).
(published in the Proc. of 14th Int. Symposium on Experimental Algorithms (SEA 2015), Springer LNCS, vol. 9125, p. 219-231, 2015, link).
Anatolii Kostrygin (2013): Periodic planar straight-frame drawings with polynomial resolution (co-advisor: Eric Fusy).
(published in the Proc. of 11th Latin American Theoretical INformatics Symposium (LATIN 2014), Springer LNCS, vol. 8392, p. 168-179, 2014, link).

1) Compression adaptative de grands graphes (sujet détaillé)

Nous allons considérer le problème de compresser et représenter de manière compacte et efficace la connectivité d’un graphe. On s’intéressera entre autres aux réseaux complexes (en font partie les réseaux sociaux, le graphe du web, les réseaux neuronaux), ainsi qu’à d’autres classes de graphes du monde réel (tels que les maillages 3D utilisés en computer graphics). Les graphes issus d’applications du monde réel sont loin du cas aléatoire et partagent des propriétés structurelles assez surprenantes. Dans se stage on vise à faire une analyse adaptative (à la fois sur le plan théorique ainsi que experimental) des méthodes de compression des graphes, de manière à établir des évaluations rigoureuses et comparaisons précises. Le but étant de faire intervenir un ou plusieurs paramètres structurels (suite des degrées de sommets, modularity, ...), et pouvoir ainsi concevoir de nouveaux schémas de compression et représentations compactes, qui seraient plus adaptées pour certaines classes de grands graphes.

Lieu du stage:LIX (Ecole Polytechnique)

Responsable:
Luca Castelli Aleardi (LIX, Ecole Polytechnique)