G-2018-64
A tabu search for the design of capacitated rooted survivable planar networks
and 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.
Published August 2018 , 18 pages
Research Axes
Research application
Publication
Dec 2020
and
Journal of Heuristics, 26(6), 829–850, 2020
BibTeX reference