Evènement pour le groupe GT Graphes et Applications

Date 2012-11-09  14:00-15: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 NP-complete 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 NP-complete 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. 
LieuSalle 178 
OrateurJulien Bensmail 
UrlLabri, Univ. de Bordeaux - CNRS 

Aucun document lié à cet événement.

Retour à l'index