%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}


% End LIPICS stuff

% -- Added Packages --
\usepackage{mathtools}
\usepackage{tikz}
\definecolor{cadmiumgreen}{rgb}{0.0, 0.42, 0.24}
\definecolor{dark-blue}{rgb}{0.05,0.25,1}
\usepackage{tcolorbox}
\usetikzlibrary{patterns,arrows,decorations.pathreplacing}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{
    colorlinks = true,
    linkcolor = blue,
    citecolor=blue
    }
\usepackage[noabbrev,capitalise,nameinlink]{cleveref}
\newcommand\claimref[2]{\hyperref[{#1}]{#2}}

\newcommand{\nc}[1]{\newcommand{#1}}
\newcommand{\Oof}{\mathcal{O}}
\newcommand{\Cc}{\mathscr{C}}
\newcommand{\Aa}{\mathcal{A}}
\newcommand{\Bb}{\mathcal{B}}
\newcommand{\Tt}{\mathcal{T}}
\newcommand{\Nn}{\mathcal{N}}
\newcommand{\Ss}{\mathcal{S}}
\newcommand{\Pp}{\mathcal{P}}
\newcommand{\Qq}{\mathcal{Q}}
\newcommand{\Rr}{\mathcal{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\minor}{\preceq}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\nc{\e}{\epsilon}
\nc{\dd}{\delta}

% -- End of added Packages --

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % For commenting the text % % % % % % % % % % % % % %
\newcommand{\commentmargin}[1]{\marginpar{\tiny\textit{#1}}}
\newcommand{\commenttext}[1]{ \begin{center} {\fbox{\begin{minipage}[h]{0.9 \linewidth}   {\sf #1} \end{minipage} }} \end{center}}

% Add your name and pick a color !
\newcommand{\alex}[1]{{\color{blue}\commenttext{Alex: #1}}}
\newcommand{\alexpb}[1]{{\color{purple}\commenttext{ATTENTION (Alex): #1}}}
\newcommand{\alexmargin}[1]{\commentmargin{\color{blue}Alex: #1}}



\newcommand{\sebi}[1]{{\color{red}\commenttext{Sebi: #1}}}
\newcommand{\sebimargin}[1]{\commentmargin{\color{red}Sebi: #1}}

\newcommand{\nicole}[1]{{\color{green!60!black}\commenttext{Nicole: #1}}}
\newcommand{\nicolemargin}[1]{\commentmargin{\color{green!60!black}Nicole: #1}}

%\newcommand{\red}[1]{{\color{red}#1}}
%%% uncomment what follows to remove the comments %%%

% \renewcommand{\commentmargin}[1]{}
% \renewcommand{\commenttext}[1]{}
% \renewcommand{\red}[1]{}

% % % % % % % % % % % % % % End commenting the text % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %


\begin{document}
\newpage


%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Calcul distribué d'ensembles dominants pour graphes planaires et d'expansion bornée.}
%

% Pour le sommaire
\addcontentsline{toc}{section}{Calcul distribué d'ensembles dominants pour graphes planaires et d'expansion bornée.}
%

% Pour la liste des auteurs
\index{Heydt, O.}\index{Kublenz, S.}\index{Siebertz, S.}\index{Vigny, A.}
%

% Citer un par un les auteurs et leur affiliation
\indent
Ozan Heydt, University of Bremen, Germany, {\tt heydt@uni-bremen.de}\\
\indent
Simeon Kublenz, University of Bremen, Germany, {\tt kublenz@uni-bremen.de}\\
\indent
Sebastian Siebertz, University of Bremen, Germany, {\tt siebertz@uni-bremen.de}\\
\indent
\underline{Alexandre Vigny}, University of Bremen, Germany, {\tt vigny@uni-bremen.de}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

Dans le modèle de calcul {\em distribué LOCAL}, le système est modélisé par un graphe $G$,
dans lequel chaque sommet représente une entité de calcul, et chaque arête représente un canal de communication.
Initialement, les sommets n'ont aucune connaissance de la topologie du graphe $G$.
Ils doivent alors communiquer et coordonner leurs actions en se transmettant des messages afin de parvenir à un
objectif commun.
% Le plus souvent, l'objectif est déterminer une propriété du réseau~: l’existence d'un motif quelque part dans le graphe, la taille d'un ensemble dominant minimale, etc.

De nombreux travaux prouvent l'existence d'algorithmes qui, en un nombre fixé de tours de communication,
produisent une approximation d'un ensemble dominant minimal. Ces algorithmes nécessitent des restrictions structurelles sur les graphes sous-jacents (graphes planaires, qui excluent un mineur, etc.).  Les objectifs sont:
\begin{itemize}
  \item d'obtenir de meilleures approximations,
  \item d'obtenir des algorithmes qui fonctionnent pour des classes de graphes les plus générales possibles.
\end{itemize}
Une liste d'articles de Czygrinow  et.~al.~débouche sur un algorithme distribué calculant une
approximation (à facteur constant) d'un ensemble dominant minimal~\cite{czygrinow2018distributed}.
Cet algorithme nécessite que le graphe donné exclut une clique comme mineur.

\bigskip
Avec Simeon Kublenz et Sebastian Siebertz, nous avons produit un algorithme qui calcule une approximation (à facteur constant)
d'un ensemble dominant minimal pour les graphes d'expansion bornée~\cite{kublenz2020distributed}.

Enfin, avec Ozan Heydt et Sebastian Siebertz, nous étudions la complexité de ce nouvel algorithme pour les graphes planaires.

\begin{thebibliography}{99}

\bibitem{czygrinow2018distributed}
A.~Czygrinow, M.~Hanckowiak, W.~Wawrzyniak, and M.~Witkowski, \emph{Distributed approximation algorithms for the minimum dominating set in $K_h$-minor-free graphs.} ISAAC 2018.

\bibitem{kublenz2020distributed}
S.~Kublenz, S.~Siebertz, and A.~Vigny, \emph{Constant round distributed domination on graph classes with bounded expansion}, SIROCCO 2020.



\end{thebibliography}


\vfill
\end{document}
