Mathematical formulations for the Balanced Vertex k-Separator Problem
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014), Mathematical formulations for the Balanced Vertex k-Separator Problem, 2014 International Conference on Control, Decision and Information Technologies (CoDIT), IEEE : Piscataway, NJ, p. 176-181. 10.1109/CoDIT.2014.6996889
TypeCommunication / Conférence
Book title2014 International Conference on Control, Decision and Information Technologies (CoDIT)
MetadataShow full item record
Mahjoub, Ali Ridha
Abstract (EN)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.
Subjects / Keywordsgraph theory
Showing items related by title and author.
Combinatorial optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systems. Martin, Sébastien; Mahjoub, Ali Ridha; Lacroix, Mathieu (2011) Article accepté pour publication ou publié
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié