Mathematical Formulations for the Balanced Vertex k-Separator Problem - Université de Lorraine Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Mathematical Formulations for the Balanced Vertex k-Separator Problem

Résumé

Given an indirected graph G = (V, E), a Vertex k-Separator is a subset of the vertex set V such that, when the separator is removed from the graph, the remaining vertices can be partitioned into k subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced Vertex k-Separator Problem, i.e., the problem of finding a minimum cardinality separator such that the sizes of the resulting disconnected subsets are balanced. We present a compact Integer Linear Programming formulation for the problem, and present a polyhedral study of the associated polytope. We also present an Exponential-Size formulation, for which we derive a column generation and a branching scheme. Preliminary computational results are reported comparing the performance of the two formulations on a set of benchmark instances.

Mots clés

Fichier non déposé

Dates et versions

hal-01267625 , version 1 (04-02-2016)

Identifiants

  • HAL Id : hal-01267625 , version 1

Citer

Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, A. Ridha Mahjoub, et al.. Mathematical Formulations for the Balanced Vertex k-Separator Problem. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.176-181. ⟨hal-01267625⟩
115 Consultations
2 Téléchargements

Partager

Gmail Facebook X LinkedIn More