SAMOVAR UMR 5157

  • Accueil
  • Accueil
  • Accueil
  • Accueil

CNRS

Rechercher




Accueil > Équipes > METHODES > Séminaires Méthodes > Séminaires METHODES > Séminaires 2012 METHODES

"Le problème du k-séparateur"

"Le problème du k-séparateur"

jeudi 18 octobre à 14h00 en salle C06 à TELECOM SudParis.

Vous trouverez ci-dessous le titre, le résumé et le nom du présentateur de chaque exposé.

Exposé de Mohamed Ahmed MOHAMED SIDI (doctorant) :

"Le problème du k-séparateur"

Résumé : Etant donné un graphe non orienté, des poids associés aux sommets du graphe et un nombre k, nous voulons calculer un k-séparateur de poids total minimum, où un k-séparateur est un ensemble de sommets dont la suppression détruit toutes les composantes connexes de tailles strictement supérieures à k. Ce problème admet de multiples applications (réseaux sociaux, passerelles dans un réseau de télécommunications, nœuds à vacciner pour arrêter une épidémie, décomposition de matrices pour faciliter la résolution de systèmes linéaires, etc.).

Nous présentons quelques facettes du problème du k-séparateur : plusieurs cas particuliers qui se résolvent polynomialement, multiples formulations mathématiques, étude polyédrique, algorithmes d’approximation en plus de quelques résultats numériques.


Exposé de Pierre Olivier Bauguion (doctorant) :

"An efficient tree-based model for multicommodity flow problems"

Abstract : Routing optimization in telecommunication networks is based on the solution of multicommodity flow problems.

In this talk, we propose a new way to model multicommodity flow problems. The flows of commodities sharing a same source node are routed on a set of trees. For any tree rooted at a given source, the same proportion of all demands, originating at this source, is routed on the tree towards the destinations. To assess the efficiency of our approach, we apply it to the Maximum Concurrent Flow problem, which is known to be among the most difficult continuous multicommodity flow problems. We show that this tree-based model is exact, in other words, restricting flows to be routed on trees does not induce any reduction in the maximum concurrent flow value. Compared to the classical path-based approach, the new approach involves much less variables, while the pricing problem remains essentially the same, namely computing shortest-path trees. This leads to a drastic reduction of computing times as shown by our computational experiments. Finally, we provide a strongly polynomial-time algorithm for the special case where all commodities share the same source.

____________________________________