Back

# A tabu search for the design of capacitated rooted survivable planar networks

## Alain Hertz and Thomas Ridremont

BibTeX reference

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.

, 18 pages

### Publication

and
Journal of Heuristics, 26(6), 829–850, 2020 BibTeX reference