Elastic time computation in QoS-driven hypermedia presentations

The development of hypermedia/multimedia systems requires the implementation of an element, usually known as formatter, which is in charge of receiving the specification of a document and controlling its presentation. Adjustments over the duration of media objects is one of the most important adaptation techniques that hypermedia formatters should implement in order to maintain document spatio-temporal relationships. Elastic time computation accomplishes this goal by stretching or shrinking the ideal duration of media objects. This paper presents new elastic time algorithms for adjusting hypermedia document presentations. The algorithms explore the flexibility offered by some hypermedia models in the definition of media-object durations, choosing objects to be stretched or shrunk in order to obtain the best possible quality of presentation. Our proposals are based on the “out-of-kilter” method for minimum-cost flow problems on temporal graphs. An aggregation procedure enhances the basic algorithm offering more flexibility in modeling real-life situations in comparison with other previous work based on linear programming.