%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{L. Bénéteau, J. Chalopin, V. Chepoi et Y. Vaxès  : Fonction 
barycentre des 
graphes médians}
%

% Pour le sommaire
\addcontentsline{toc}{section}{L. Bénéteau, J. Chalopin, V. Chepoi et Y. Vaxès  
: Barycentre des 
	graphes médians en temps linéaire}
%

% Pour la liste des auteurs
\index{Bénéteau, L.}\index{Chalopin, J.}\index{Chepoi, V.}\index{Vaxès, Y.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Laurine Bénéteau}, LIS, Marseille, {\tt 
laurine.beneteau@lis-lab.fr}\\%souligner l'orateur
\indent
Jérémie Chalopin, LIS, Marseille, {\tt jeremie.chalopin@lis-lab.fr}\\ 
\indent
Victor Chepoi, LIS, Marseille, {\tt victor.chepoi@lis-lab.fr}\\ 
\indent
Yann Vaxès, LIS, Marseille, {\tt yann.vaxes@lis-lab.fr}\\ 
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

Le problème du barycentre consiste, étant donné un graphe $G=(V,E)$ et 
un ensemble fini de sommets $S$, à trouver un sommet de $G$ minimisant la 
fonction 
barycentre $B_S(v)=\sum_{s\in S}d^2(v,s)$, soit la somme du carré des distances 
vers tous les sommets de 
$S$.

Un graphe $G=(V,E)$ est dit médian si pour tout triplet de sommets $u,v,w$ de 
$V$, il existe un unique sommet qui est à la fois sur un plus court chemin de 
$u$ à $v$, de $u$ à $w$ et de $v$ à $w$.
Dans un travail précédent, nous avons proposé un algorithme linéaire permettant 
de calculer la fonction médiane $M_S$ pour un sous-ensemble de sommets $S$ d'un 
graphe médian $G$, i.e., de calculer pour tout $v \in V$, $M_S(v) = \sum_{s\in 
S} d(v,s)$.

Nous proposons un algorithme linéaire qui permet de calculer en chaque sommet 
$v$ d'un graphe médian $G$ la fonction barycentre $B_S(v)$.

L'algorithme utilise une propriété structurelle fondamentale des 
graphes médians : on peut partitionner les arêtes par classe d'équivalence avec 
une fonction $\Theta$. On les appelle des $\Theta$-classes, et la suppression 
de 
chacune de ces classes 
d'équivalence partitionne 
le graphe en deux sous graphes appelés demi-espaces, qui sont convexes, portés 
et également médians. Cette partition peut être calculée en temps linéaire.

Ceci nous permet d'appliquer un algorithme récursif 
dont voici l'idée principale:
Étant donné une arête $uv$, une formule permet d'obtenir la valeur de la 
fonction barycentre en $u$ à partir de la valeur de la fonction barycentre en 
$v$. Cette formule nécessite de connaître la valeur de la fonction médiane en 
$u$ pour un des demi-espaces définis par l'arête $uv$. Pour obtenir 
efficacement cette information, on utilise une propriété qui permet de calculer 
la valeur de la fonction médiane dans tous les sommets d'un 
sous-graphe porté $H$ de $G$ en temps proportionnel à la taille de $H$ (et pas 
à celle de $G$). 
On en déduit un 
algorithme qui calcule la valeur de la fonction barycentre en chaque sommet 
d'un graphe médian en temps linéaire.


\vfill
\end{document}
