Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
On parameterized Multiroute-Flow : an efficient tool to manage failures resistance in a network
Jean-François BAFFIER

09 March 2012, 10h30 - 09 March 2012, 11h30
Salle/Bat : 455/PCRI-N
Contact :

Activités de recherche :

Résumé :
A K-route channel is a communication path that goes through K edge-disjoint paths, providing a resistance up to K-1 edge failures. A K-route-flow (a multiroute flow of K routes) is a sum of K-route channels respecting the network capacities constraint. It provides a lower bound of the max-flow value in a case of K-1 edges failures. A max-flow/min-cut theorem in the K-route context has been proved by Kishimoto and Takeuchi. This results can be easily extended to include node failures.

Given a network with one variable edge, we study the impact of the variation of this edge's capacity on the multiroute flow in a general case (previous work already treated the case of 1-route-flow and 2-route- flow). For any integer K, we show that a max-K-flow solution is a piecewise linear function (with at most K +1 changes of slope that we call critical points). We provide a polynomial algorithm which gives us all the critical points for a given source/sink pair. We also extend the function analysis to the case with any number of variable edges.

Pour en savoir plus :
Séminaires
Programmation mathématique multi-objectif pour la
Thursday 13 December 2018 - 14h30
Salle : unknown - unknown
Audrey Legendre .............................................

Redundancy in Distributed Proofs
Algorithmique distribuée
Tuesday 04 December 2018 - 00h00
Salle : 465 - PCRI-N
Ami Paz .............................................

Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Scalable and exhaustive screening of metabolic fun
Wednesday 28 November 2018 - 11h00
Salle : 465 - PCRI-N
Clémence Frioux .............................................

Studying the three-dimensional structure of DNA fr
Thursday 22 November 2018 - 15h00
Salle : unknown - unknown
Nelle Varoquaux .............................................