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
Type
Communication / ConférenceDate
2014Book title
2014 International Conference on Control, Decision and Information Technologies (CoDIT)Publisher
IEEE
Published in
Piscataway, NJ
ISBN
978-1-4799-6773-5
Pages
176-181
Publication identifier
Metadata
Show full item recordAuthor(s)
Cornaz, DenisFurini, Fabio
Lacroix, Mathieu

Malaguti, Enrico
Mahjoub, Ali Ridha
Martin, Sébastien

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 / Keywords
graph theoryRelated items
Showing items related by title and author.
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2015) Communication / Conférence
-
Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié