Minimum convex piecewise linear cost tension problem on quasi-k series-parallel graphs

This article proposes an extension, combined with the out-of-kilter technique, of the aggregation method (that solves the minimum convex piecewise linear cost tension problem, or CPLCT, on series-parallel graphs) to solve CPLCT on quasi series-parallel graphs. To make,this algorithm efficient, the key point is to find a "good" way of decomposing t he graph into series-parallel subgraphs. Decomposition techniques, based on the recognition of series-parallel graphs, are thoroughly discussed. Keywords: minimum cost tension, series-parallel graph, graph decomposition, series-parallel