Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 21 Juin 2016

Decomposing Cubic Graphs into Connected Subgraphs of Size Three

par Laurent Bulteau (LIGM, Marne-la-Vallée)

Let S be the set of connected graphs with three edges (S contains the triangle, the claw, and the path on 4 vertices). We study the problem of partitioning the edge set of a graph G into graphs taken from S or, more generally, from any non-empty subset S' of S. The problem is known to be NP-complete for any possible choice of S' in general graphs. In this talk, we assume that the input graph is cubic, and study the computational complexity of the problem of partitioning its edge set for any choice of S’. We identify all polynomial and NP-complete problems in that setting, and give graph-theoretic characterizations of S'-decomposable cubic graphs in some cases.

(joint work with Guillaume Fertin, Anthony Labarre, Romeo Rizzi and Irena Rusu)

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr