|
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. |
Lieu | Salle 178 |
Orateur | Julien Bensmail |
Url | Labri, Univ. de Bordeaux - CNRS |
Aucun document lié à cet événement. RetourRetour à l'index
| |