%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[french]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Robustesse des distances et du diamètre dans un réseau qui se détériore}
%

% Pour le sommaire
\addcontentsline{toc}{section}{A. Casteigts, T. Corsini, H. Hocquard, A. Labourel : Robustesse des distances et du diamètre dans un réseau qui se détériore}
%

% Pour la liste des auteurs
\index{Casteigts, A.}\index{Corsini, T.}\index{Hocquard, H.}\index{Labourel, A.}
%

% Citer un par un les auteurs et leur affiliation
Arnaud Casteigts, LaBRI, Bordeaux, {\tt arnaud.casteigts@labri.fr}\\
\indent
\underline{Timothée Corsini}, LaBRI, Bordeaux, {\tt timothee.corsini@labri.fr}\\ %souligner l'orateur
\indent
Hervé Hocquard, LaBRI, Bordeaux, {\tt hocquard@labri.fr}\\
\indent
Arnaud Labourel, LIS, Aix-Marseille, {\tt arnaud.labourel@lis-lab.fr}\\
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

Une propriété d'un graphe $G$ est robuste si elle est satisfaite dans tous les sous-graphes couvrants connexes de $G$~\cite{robustness}.
Cette notion de robustesse est un type d'hérédité de propriété motivée par les réseaux dynamiques.
Nous allons présenter des résultats sur la caractérisation des graphes ayant un diamètre robuste. 
Le diamètre est important en algorithmique distribuée car il intervient souvent comme paramètre de complexité des algorithmes. Le fait qu'il soit robuste implique alors que la complexité ne se dégradera pas à mesure que le réseau se détériore (c.à.d. perd des liens définitivement), du moment qu'il reste connexe.
Nous montrerons que le problème de décider si le diamètre d'un graphe est robuste est co-NP-complet. À l'inverse, décider si la distance entre deux sommets donnés est robuste peut se faire simplement en adaptant un algorithme de reconnaissance des graphes série-parallèle.

\smallskip

%Si vous souhaitez ajouter une figure, faites-en sorte qu'elle soit
%compilable par {\tt pdflatex} (pas de {\tt pstricks} ou d'{\tt eps}). Vous pouvez aussi
%utiliser tikz si vous le souhaitez.

\smallskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Eventuellement, une figure, pdf ou png (PAS eps)
%\begin{figure}[htb]
%\begin{center}
%\includegraphics[height=3cm]{gtree}
%\caption{Un graphe.
%\label{fig:graphe}}
%\end{center}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{99}

\bibitem{robustness}
Arnaud Casteigts, Swan Dubois, Franck Petit, and John M Robson, \emph{Robustness: A new form of heredity motivated by dynamic networks},
Theoretical Computer Science {\bf 806} (2020), 429--445.

%\bibitem{nk1}
%N.~Trotignon and K.~Vu{\v s}kovi{\'c}, \emph{A structure theorem for graphs with no cycle with a unique chord and
%  its consequences}, J. Graph Theory {\bf 63(1)} (2010), 31--67.
%
\end{thebibliography}


\vfill
\end{document}