Retour

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 TV of terminals, and an integer k, we aim at selecting a minimum cost subset AA 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

Axes de recherche

Application de recherche

Publication