Ce jeudi 14 octobre à 14h, Anthony Labarre de l’Université Gustave Eiffel de Marne-la-Vallée nous présentera son travail réalisé en collaboration avec Laurent Bulteau, Guillaume Fertin, Romeo Rizzi et Irena Rusu intitulé “Décomposition de graphes sous-cubiques à l’aide d’étoiles, de chemins et de triangles” dont voici un résumé :
Un problème classique d’algorithmique des graphes consiste à calculer une partition des arêtes d’un graphe sous diverses contraintes. On peut par exemple exiger que les morceaux dans la décomposition du graphe suivent une certaine structure; par exemple, que tous les morceaux obtenus soient des chemins, ou possèdent un certain nombre d’arêtes. Si S est un ensemble de graphes fixé, une “S-décomposition” d’un graphe G est une partition de ses arêtes telle que tous ses morceaux sont isomorphes à un élément de S. Décider si une telle décomposition existe s’avère être un problème difficile même dans le cas où S ne contient qu’un seul graphe avec un morceau contenant au moins trois arêtes, ce qui nous pousse naturellement à chercher des cas particuliers que l’on arrive à résoudre en temps polynomial. J’étudie dans ce travail une version restreinte où G est sous-cubique (chaque sommet possède au plus trois voisins) et où les morceaux autorisés sont connexes et possèdent exactement trois arêtes. J’identifie sous ces contraintes tous les cas solubles en temps polynomial, et tous les cas qui restent difficiles.
Séminaire ouvert à tous. La présentation aura lieu à l’ICHEC, site Anjou à 14h00. Pour faciliter l’organisation, merci de vous inscrire auprès de quaresmi@ichec.be.
Au plaisir de vous y voir nombreux.