Méthode de reconstruction pour la synchronisation hypermédia de SP-graphes

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.

Le 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 avec des coûts convexes linéaires par morceaux, nous avons étudié différentes approches (programmation linéaire, mise à conformité - out-of-kilter, mise à l'échelle du dual - cost-scaling). Cependant, ces méthodes ont été conçues pour des graphes quelconques.

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, et les méthodes élaborées pour une structure de graphe quelconque ne s'avèrent pas toujours très efficaces. Nous avons donc proposé une méthode polynômiale, O(m³), plus adaptée pour résoudre le problème sur des graphes série-parallèles, et que nous avons appelée agrégation.

Mais ces graphes, bien que très proches de la réalité, restent encore une idéalisation. Nous proposons de mesurer l'aspect série-parallèle d'un graphe en définissant la notion de graphe presque série-parallèle, basée sur la décomposition du graphe en composantes série-parallèles. Nous discutons alors de deux problèmes: tout d'abord comment décomposer au mieux un graphe quelconque en composantes série-parallèles, et ensuite comment profiter de cette décomposition et de l'efficacité de la méthode d'agrégation pour déterminer efficacement une tension optimale du graphe original. Nous appelons cette approche reconstruction, puisqu'elle consiste à reconstituer progressivement le graphe original à partir d'une décomposition en composantes série-parallèles, en maintenant tout au long de la reconstruction une tension minimale.