
Evènement pour le groupe GT Graphes et Applications
Date  20121109 14:0015:00 
Titre  Computational complexity of partitioning a graph into a few connected subgraphs 
Résumé  Let G be a graph. A sequence τ = (n'_1_', ... , n'_k_') of positive integers summing up to V(G) is realizable in G if there exists a partition (V'_1_', ..., V'_k_') of V(G) such that each V'_i_' induces a connected subgraph of G on n'_i_' vertices. Deciding whether τ is realizable in G was proven to be a NPcomplete problem in general, even when τ contains only one integer value or G is a tree with maximum degree 3. In this talk, we will show that this problem remains NPcomplete even when τ has only 2 elements. This result involves that there is no constant threshold on the size of τ under which the problem above becomes easy. Additionally, we will introduce some other graph partition problems and locate them in the second level of the polynomial hierarchy. 
Lieu  Salle 178 
Orateur  Julien Bensmail 
Url  Labri, Univ. de Bordeaux  CNRS 
Aucun document lié à cet événement. RetourRetour à l'index
 