dc.contributor.author | Cornaz, Denis | * |
dc.contributor.author | Furini, Fabio | * |
dc.contributor.author | Lacroix, Mathieu | * |
dc.contributor.author | Malaguti, Enrico | * |
dc.contributor.author | Mahjoub, Ali Ridha | * |
dc.contributor.author | Martin, Sébastien | * |
dc.date.accessioned | 2019-06-11T10:33:51Z | |
dc.date.available | 2019-06-11T10:33:51Z | |
dc.date.issued | 2019 | |
dc.identifier.issn | 1572-5286 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/18969 | |
dc.language.iso | en | en |
dc.subject | Vertex cut | en |
dc.subject | Mixed-integer programming models | en |
dc.subject | Branch and Price | en |
dc.subject | Exact algorithms | en |
dc.subject.ddc | 005 | en |
dc.title | The vertex k-cut problem | en |
dc.type | Article accepté pour publication ou publié | |
dc.description.abstracten | Given 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.isversionofjnlname | Discrete Optimization | |
dc.relation.isversionofjnlvol | 31 | en |
dc.relation.isversionofjnldate | 2019-02 | |
dc.relation.isversionofjnlpages | 8-28 | en |
dc.relation.isversionofdoi | 10.1016/j.disopt.2018.07.003 | en |
dc.relation.isversionofjnlpublisher | Elsevier | en |
dc.subject.ddclabel | Programmation, logiciels, organisation des données | en |
dc.relation.forthcoming | non | en |
dc.relation.forthcomingprint | non | en |
dc.description.ssrncandidate | non | en |
dc.description.halcandidate | oui | en |
dc.description.readership | recherche | en |
dc.description.audience | International | en |
dc.relation.Isversionofjnlpeerreviewed | oui | en |
dc.relation.Isversionofjnlpeerreviewed | oui | en |
dc.date.updated | 2019-06-11T10:28:19Z | |
hal.person.labIds | 989 | * |
hal.person.labIds | 989 | * |
hal.person.labIds | 994 | * |
hal.person.labIds | 461036 | * |
hal.person.labIds | 989 | * |
hal.person.labIds | 234725 | * |
hal.identifier | hal-02152319 | * |