Tension minimum à coûts convexes linéaires par morceaux dans les quasi SP-graphes

Cet article propose une extension, combinée avec la technique de mise-à-conformité, de la méthode d'agrégation (qui résout le problème de tension minimum à coûts convexes linéaires par morceaux, ou CPLCT, sur des graphes série-parallèles) afin de résoudre CPLCT sur des graphes quasi série-parallèles. Pour rendre cet algorithme efficace, le point clé est de trouver une "bonne" décomposition du graphe en sous-graphes série-parallèles. Des techniques de décomposition, basées sur la reconnaissance de graphes série-parallèles, sont discutées en détails.