Show simple item record

The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCornaz, Denis*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMagnouche, Youcef*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Ali Ridha*
hal.structure.identifierLaboratoire de Conception, Optimisation et Modélisation des Systèmes [LCOMS]
dc.contributor.authorMartin, Sébastien
HAL ID: 9612
ORCID: 0000-0001-8980-8628		*
dc.date.accessioned2019-07-17T10:28:55Z
dc.date.available2019-07-17T10:28:55Z
dc.date.issued2019
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19249
dc.language.isoenen
dc.subjectVertex separator problemen
dc.subjectInteger programmingen
dc.subjectPolytopeen
dc.subjectFaceten
dc.subjectBranch-and-Cut algorithmen
dc.subjectComplexityen
dc.subjectSeparation algorithmen
dc.subject.ddc519en
dc.titleThe multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cuten
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol256en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2019-03
dc.relation.isversionofjnlpages11-37en
dc.relation.isversionofdoi10.1016/j.dam.2018.10.005en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-07-17T10:20:52Z
hal.identifierhal-02186511*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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