%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*{Preprocessing algorithm for optimizing the ecological connectivity of landscapes}
%

% Pour le sommaire
\addcontentsline{toc}{section}{C. Albert, B. Cou ̈etoux, F. Hamonic, Y. Vax`es : Preprocessing algorithm for optimizing the landscape connectivity of an ecological network}
%

% Pour la liste des auteurs
\index{Albert, C.}\index{Couëtoux, B.}\index{Hamonic, F.}\index{Vaxès, Y.}
%

% Citer un par un les auteurs et leur affiliation
Cécile Albert, IMBE, Marseille, {\tt cecile.albert@imbe.fr}\\
\indent
Basile Couëtoux, LIS, Marseille, {\tt basile.couetoux@lis-lab.fr}\\
\indent
\underline{François Hamonic}, LIS, Marseille, {\tt francois.hamonic@lis-lab.fr}\\
\indent
Yann Vaxès, LIS, Marseille, {\tt yann.vaxes@lis-lab.fr}\\
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

The \textit{landscape connectivity} has been defined as the degree to which a landscape facilitates the movement of individuals between habitat areas (Taylor et al, 1993). Beyond the capacity of moving around to access vital resources, landscape connectivity increases gene flow among populations and improves their adaptability to climate change.

An ecological landscape can be viewed as a directed graph $G=(V,A)$ in which vertices represent habitat areas and arcs represent ecological corridors to travel between them.
The equivalent connected area $ECA(G)$ is computed from all pair shortest path distances in this weighted graph and is used by ecologists to assess the ecological connectivity (Saura \& Pascual-Hortal, 2007). Each arc $a=(u,v)$ has a length $l^+_a$ that represents how difficult it is to travel from $u$ to $v$ and a cost $c_a$ for reducing this length to $l^-_a.$ In \cite{ARXIV_PAPIER_NETWORKS}, we have proposed a mixed integer program for the problem of computing a subset $S \subseteq A$ of cost at most $B$ that maximizes $ECA(G')$ where $G'$ is the graph obtained from $G$ by reducing the length of each arc $a \in S$ from $l^+_a$ to $l^-_a.$ For landscapes with few hundred nodes the MIP size exceeds the capacity of standard MIP solvers.

This motivates the study of the following algorithmic problem that could be of independent interest. Let $\cal L$ be the set of length functions $l$ such that $l_a \in \{l^-_a,l^+_a\}$ for every arc $a \in A.$ Let $d_l(s,t)$ be the length of the shortest $st$-path with respect to the length function $l.$
An arc $(u,v)$ is said to be \textit{$t$-strong} (resp. \textit{$t$-useless}) if $d_l(u,t)=l(u,v)+d_l(v,t)$ (resp. $d_l(u,t) < l(u,v)+d_l(v,t)$) for every $2^{|A|}$ length functions $l\in {\cal L.}$
Given an oriented graph $G,$ an arc $(u,v)$ and two length functions $l^+$ and $l^-,$ we provide a $O(|A| + |V| \log |V|)$ algorithm that computes the set of vertices $t$ such that $(u,v)$ is $t$-strong (resp. $t$-useless).
Our experiments show that decreasing the size of the network by contracting strong arcs and removing useless arcs allows to compute optimal connectivity improvement for significantly larger ecological landscapes.\\

[1] F.~Hamonic, C.~Albert, B.~Couëtoux, Y.~Vaxès,  \emph{Optimizing the ecological connectivity of landscapes with generalized flow models and preprocessing}, https://arxiv.org/abs/2109.06622.

% {
%     \begin{thebibliography}{99}
%         \bibitem{ARXIV_PAPIER_NETWORKS}
%         F.~Hamonic, C.~Albert, B.~Couëtoux, Y.~Vaxès,  \emph{Optimizing the ecological connectivity of landscapes with generalized flow models and preprocessing}, https://arxiv.org/abs/2109.06622.
%     \end{thebibliography}
% }

\vfill
\end{document}
