Given a directed graph
\(G=(V,A)\), capacity and cost functions on
\(A\), a root
\(r\), a subset
\(T \subset V\) of terminals, and an integer
\(k\), we aim at selecting a minimum cost subset
\(A'\subseteq A\) such that for every subgraph of
\(G'=(V,A')\) obtained by removing
\(k\) arcs from
\(A'\) it is possible to route one unit of flow from
\(r\) to each terminal while respecting the capacity constraints.
We focus on the case where the input graph
\(G\) is planar and propose a tabu search algorithm whose main procedure takes advantage of planar graph duality properties.
Published August 2018 , 18 pages