Given an undirected graph G=(V,E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k components. Given a graph G and an integer k≥2, the vertex k-cut problem consists in finding a vertex k-cut of G of 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.
The vertex k-cut problem / Cornaz D.; Furini F.; Lacroix M.; Malaguti E.; Mahjoub A.R.; Martin S.. - In: DISCRETE OPTIMIZATION. - ISSN 1572-5286. - STAMPA. - 31:(2019), pp. 8-28. [10.1016/j.disopt.2018.07.003]
The vertex k-cut problem
Malaguti E.;
2019
Abstract
Given an undirected graph G=(V,E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k components. Given a graph G and an integer k≥2, the vertex k-cut problem consists in finding a vertex k-cut of G of 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.File | Dimensione | Formato | |
---|---|---|---|
VKS_full.pdf
Open Access dal 15/09/2020
Tipo:
Postprint
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione
764.61 kB
Formato
Adobe PDF
|
764.61 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.