Show simple item record

The vertex k-cut problem

dc.contributor.authorCornaz, Denis*
dc.contributor.authorFurini, Fabio*
dc.contributor.authorLacroix, Mathieu*
dc.contributor.authorMalaguti, Enrico*
dc.contributor.authorMahjoub, Ali Ridha*
dc.contributor.authorMartin, Sébastien*
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.person.labIds989*
hal.person.labIds989*
hal.person.labIds994*
hal.person.labIds461036*
hal.person.labIds989*
hal.person.labIds234725*
hal.identifierhal-02152319*


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