Tension de coût minimum dans un graphe série-parallèle ou presque

Les formats actuels de diffusion de documents sur Internet apportent sans conteste de nouvelles possibilités par rapport au support papier. Mais les exigences deviennent toujours plus grandes et de nouveaux langages font régulièrement leur apparition pour tenter d'améliorer encore la structure et l'interactivité des documents. Parmi ces langages, certains offrent la possibilité d'animer et synchroniser des composants multimédia. Mais la variété de ces composants (audio, vidéo, texte, image...) font de l'animation un problème compliqué. L'auteur d'un document synchronisé fournit une liste de contraintes temporelles sur les composants de manière à décrire le déroulement de la présentation. Ces composants ont chacun une durée de présentation qui est flexible dans une certaine limite. Tout le problème consiste à trouver un bon ajustement des durées pour que la présentation se déroule au plus proche de ce que souhaite l'auteur tout en évitant les pauses.

Ce problème peut se modéliser, après quelques restrictions, comme un problème de tension de coût minimum dans un graphe. Pour le résoudre, nous avons étudié différentes approches (programmation linéaire, mise à conformité - out-of-kilter, mise à l'échelle du dual - cost-scaling) dont nous proposons un récapitulatif et un comparatif sur les plans théorique et pratique. Cependant, les tests numériques ont été réalisés sur des graphes complètement aléatoires.

Les graphes représentant les contraintes temporelles sont en réalité très structurés et très proches de la classe des graphes appelés série-parallèles. Nous montrons tout d'abord par des résultats numériques que les méthodes déjà proposées ne sont pas toujours très efficaces. Nous présentons alors une méthode adaptée que nous appelons agrégation et qui, comparée aux méthodes précédentes, s'avère très efficace pour résoudre le problème sur des graphes série-parallèles. Mais ces graphes, bien que très proches de la réalité, restent encore une idéalisation. Nous proposons alors nos premières réflexions et un algorithme pour résoudre le problème de tension de coût minimum sur des graphes quasiment série-parallèles, en essayant d'exploiter au mieux la méthode d'agrégation.