Show simple item record

The vertex k-cut problem

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.authorFurini, Fabio*
hal.structure.identifierLaboratoire d'Informatique de Paris-Nord [LIPN]
dc.contributor.authorLacroix, Mathieu
HAL ID: 741352
ORCID: 0000-0001-8385-3890		*
hal.structure.identifierD.E.I. - University of Bologna.
dc.contributor.authorMalaguti, Enrico*
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-06-11T10:33:51Z
dc.date.available2019-06-11T10:33:51Z
dc.date.issued2019
dc.identifier.issn1572-5286
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18969
dc.language.isoenen
dc.subjectVertex cuten
dc.subjectMixed-integer programming modelsen
dc.subjectBranch and Priceen
dc.subjectExact algorithmsen
dc.subject.ddc005en
dc.titleThe vertex k-cut problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven an undirected graph G=(V, E), a vertex k-cut of G is a vertex subset of the removing of which disconnects the graph in at least components. Given a graph and an integer k≥2, the vertex k-cut problem consists in finding a vertex k-cut of of G minimum cardinality. We first prove that the problem is NP-hard for any fixed k≥3. We then present a compact formulation, and an extended formulation from which we derive a column generation and a branching scheme. Extensive computational results prove the effectiveness of the proposed methods.en
dc.relation.isversionofjnlnameDiscrete Optimization
dc.relation.isversionofjnlvol31en
dc.relation.isversionofjnldate2019-02
dc.relation.isversionofjnlpages8-28en
dc.relation.isversionofdoi10.1016/j.disopt.2018.07.003en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donné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-06-11T10:28:19Z
hal.identifierhal-02152319*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
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