Minimum convex-cost tension problems on series-parallel graphs

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piece-wise linear cost tension problems on series-parallel graphs in O(m³) operations.