dc.contributor.author Cornaz, Denis dc.contributor.author Magnouche, Youcef dc.contributor.author Mahjoub, Ali Ridha dc.contributor.author Martin, Sébastien dc.date.accessioned 2020-09-04T13:58:15Z dc.date.available 2020-09-04T13:58:15Z dc.date.issued 2015 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/20971 dc.language.iso en en dc.subject Vertex separator problem en dc.subject Integer programming en dc.subject Polytope en dc.subject Facet en dc.subject Branch-and-Cut algorithm en dc.subject Complexity en dc.subject Separation algorithm en dc.subject.ddc 519 en dc.title The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut en dc.type Communication / Conférence dc.description.abstracten In this paper we consider a variant of the k-separator problem. Given a graph G=(V∪T,E) with V∪T the set of vertices, where T is a set of k terminals, the multi-terminal vertex separator problem consists in partitioning V∪T into k+1 subsets {S,V1,...,Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study. en dc.relation.ispartoftitle 45th International Conference on Computers & Industrial Engineering 2015 (CIE45) en dc.relation.ispartofeditor Kacem, Imed dc.relation.ispartofpublname Curran Associates, Inc. en dc.identifier.urlsite https://hal.univ-lorraine.fr/hal-01785327 en dc.subject.ddclabel Probabilités et mathématiques appliquées en dc.relation.ispartofisbn 9781510817456 en dc.relation.conftitle 45th International Conference on Computers & Industrial Engineering 2015 (CIE45) en dc.relation.confdate 2015-08 dc.relation.confcity Metz en dc.relation.confcountry France en dc.relation.forthcoming non en dc.identifier.doi 10.1016/j.dam.2018.10.005 en dc.description.ssrncandidate non en dc.description.halcandidate non en dc.description.readership recherche en dc.description.audience International en dc.relation.Isversionofjnlpeerreviewed non en dc.relation.Isversionofjnlpeerreviewed non en dc.date.updated 2020-09-04T13:49:25Z hal.person.labIds 989 hal.person.labIds 989 hal.person.labIds 989 hal.person.labIds 989
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.