G-2018-64
A tabu search for the design of capacitated rooted survivable planar networks
et référence BibTeX
Given a directed graph G=(V,A)
, capacity and cost functions on A
, a root r
, a subset T⊂V
of terminals, and an integer k
, we aim at selecting a minimum cost subset A′⊆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.
Paru en août 2018 , 18 pages
Axes de recherche
Application de recherche
Publication
déc. 2020
et
Journal of Heuristics, 26(6), 829–850, 2020
référence BibTeX