Show simple item record

dc.contributor.authorCornaz, Denis
dc.contributor.authorFurini, Fabio
dc.contributor.authorLacroix, Mathieu
HAL ID: 741352
ORCID: 0000-0001-8385-3890
dc.contributor.authorMalaguti, Enrico
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorMartin, Sébastien
HAL ID: 9612
ORCID: 0000-0001-8980-8628
dc.date.accessioned2016-07-08T11:12:45Z
dc.date.available2016-07-08T11:12:45Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15619
dc.language.isoenen
dc.subjectgraph theory
dc.subject.ddc003en
dc.titleMathematical formulations for the Balanced Vertex k-Separator Problem
dc.typeCommunication / Conférence
dc.description.abstractenGiven 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.
dc.identifier.citationpages176-181
dc.relation.ispartoftitle2014 International Conference on Control, Decision and Information Technologies (CoDIT)
dc.relation.ispartofpublnameIEEE
dc.relation.ispartofpublcityPiscataway, NJ
dc.relation.ispartofdate2014
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-4799-6773-5
dc.relation.forthcomingnonen
dc.identifier.doi10.1109/CoDIT.2014.6996889
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-02-09T15:06:59Z
hal.identifierhal-01343393*
hal.version1*
hal.update.actionupdateMetadata*
hal.update.actionupdateFiles*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record