An approximation algorithm for the maximum leaf spanning arborescence problem

We present an O(vopt)-approximation algorithm for the maximum leaf spanning arborescence problem, where opt is the number of leaves in an optimal spanning arborescence. The result is based upon an O(1)-approximation algorithm for a special class of directed graphs called willows. Incorporating the method for willow graphs as a subroutine in a local improvement algorithm gives the bound for general directed graphs.Nous présentons une approximation algorithmique O(vopt) pour le probléme d'envergure maximum d'arborescence o´u opt est le nombre de feuilles dans une étendue arborescente optimal. Le résultat est basé sur une approximation algorithmique O(1) pour une classe spéciale de graphiques dirigés appelés saules. En incorporant la méthode des graphiques de saules comme une sous-routine dans une amélioration algorithmique locale nous donne le lien des graphiques dirigée généraux