Wednesday 26
Graphs, flows, combinatorial algorithms and approximation
Sébastien Morais
› 16:00 - 16:20 (20min)
› Bât B - TD 43
Solution approchée avec garantie de performance pour les problèmes de recouvrement sous contrainte sur le degré des nœuds
Massinissa Merabet  1, *@  , Sylvain Durand  1, *@  , Miklos Molnar  1, *@  
1 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier  (LIRMM)  -  Website
Université Montpellier II - Sciences et techniques, CNRS : UMR5506
CC 477, 161 rue Ada, 34095 Montpellier Cedex 5 -  France
* : Corresponding author

Le problème de recherche d'arbre de recouvrement de coût minimum sous contrainte sur le degré des noeuds B (Degree Constrained Minimum Spanning Tree, DCMST), est un problème NP-Difficile largement étudié dans la littérature. Un des domaines d'application est le routage multicast dans les réseaux optiques. Un algorithme calculant en temps polynomial un arbre de recouvrement de degré au plus B +1 a été proposé par M. Singh et L. C. Lau en 2007. Ce problème étant non approximable à facteur constant, ce résultat est le meilleur possible. Récemment, une structure plus flexible appelée «hiérarchie» a été proposée. Les hiérarchies peuvent être perçues comme une généralisation des arbres de la même façon que les chaînes sont une généralisation des chaînes élémentaires. Cette nouvelle structure n'est pas un sous-graphe mais un homomorphisme d'un arbre dans le graphe. Nous étudions le problème de la hiérarchie de recouvrement de coût minimum d'un graphe sous contrainte sur le degré des noeuds (Degree Constrained Minimum Spanning Hierarchy, DCMSH). Ce problème consiste à trouver une hiérarchie de recouvrement H de coût minimum telle que le degré de chaque sommet de H est inférieur ou égal à une borne B. Ce problème reste NP-Difficile mais nous montrons qu'il est approximable avec un ratio R = B/B−1 et que ce ratio est le meilleur que l'on puisse obtenir avec la technique utilisée.

Consulter le rapport de recherche : http://hal-lirmm.ccsd.cnrs.fr/lirmm-00907052


Online user: 1