Mathematical Formulations for the Balanced Vertex k-Separator Problem

Abstract : 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 : graph theory
Type de document :
Communication dans un congrès
Kacem, I and Laroche, P and Roka, Z. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. 2014 International Conference on Control, Decision and Information Technologies (CoDIT), pp.176-181, 2014
Liste complète des métadonnées

https://hal.univ-lorraine.fr/hal-01267625
Contributeur : Catherine Angevelle <>
Soumis le : jeudi 4 février 2016 - 16:10:09
Dernière modification le : samedi 5 mai 2018 - 01:01:46

Identifiants

  • HAL Id : hal-01267625, version 1

Citation

Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, A. Ridha Mahjoub, et al.. Mathematical Formulations for the Balanced Vertex k-Separator Problem. Kacem, I and Laroche, P and Roka, Z. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. 2014 International Conference on Control, Decision and Information Technologies (CoDIT), pp.176-181, 2014. 〈hal-01267625〉

Partager

Métriques

Consultations de la notice

99