Problèmes de tension minimum à coûts convexes dans les graphes série-parallèles

Nous présentons rapidement quelques résultats obtenus par des méthodes connues pour résoudre des problèmes de tension de coût minimum, comparant leur performance sur des graphes quelconques et sur des graphes série-parallèles. Ces graphes se montrent très intéressants pour approximer certains problèmes de tension, comme la synchronisation dans les documents hypermedia. Nous proposons une nouvelle méthode d'agrégation pour résoudre le problème de tension minimum à coûts convexes linéaires par morceaux dans les graphes série-parallèles en O(m³) opérations.