Minimum Cost Tension in a Series-Parallel or Almost Series-Parallel Graph

The actual formats used to publish documents on the Internet bring, without discussion, new facilities compared to the paper material. But needs are still growing and new languages appear regularly, attempting to improve the structure and the interactivity of documents. Among these languages, some offer the possibility of animating and synchronizing media components. But the variety of these components (audio, video, text, image...) makes the animation a difficult problem. The author of a synchronized document provides a set of temporal constraints on the components to describe the progress of the presentation. Each of these components has a duration of presentation that is flexible within some boundaries. The problem consists in finding a good adjustment of the durations so the presentation progresses as close as possible to what the author wants with avoiding any pause.

The problem can be modeled, after some restrictions, as a minimum cost tension problem in a graph. To solve it, we studied several methods (linear programming, out-of-kilter, cost-scaling on the dual) of which we propose a summary and comparisons on both theoretical and practical aspects. However, the numerical tests were performed on completely random graphs.

The graphs representing the temporal constraints are in fact very structured and very close to a class of graphs called series-parallel. We show first, through numerical results, that the methods already proposed are not always very efficient. Hence, we present an adapted method that we call aggregation, which appears to be very efficient to solve the problem on series-parallel graphs, compared to the previous methods. But these graphs, although very close to the real cases, are still an idealization. We propose then our first thoughts and an algorithm to solve the minimum cost tension problem on almost series-parallel graphs, trying to take advantage of the aggregation method the best we can.