The vertex k -cut problem
Discrete Optimization · 2019-02 · 31 · 8-28
DOI: 10.1016/j.disopt.2018.07.003 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Optimization, 2019-02. Verfasst von Denis Cornaz und 5 weiteren Autor:innen. Die Arbeit wurde bisher 20-mal zitiert (Crossref) und nennt 29 Literaturangaben. Gefördert von: Gaspard Monge Program for Optimization and operations research, MIUR, Nonlinear and combinatorial aspects of complex networks.
Abstract (Originalsprache)
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.
Förderung
- Gaspard Monge Program for Optimization and operations research
- MIUR
- Nonlinear and combinatorial aspects of complex networks
Zitieren
APA
Cornaz, D., Furini, F., Lacroix, M., Malaguti, E., Mahjoub, A. R., & Martin, S. (2019). The vertex k -cut problem. Discrete Optimization, 31, 8-28. https://doi.org/10.1016/j.disopt.2018.07.003
Vancouver
Cornaz D, Furini F, Lacroix M, Malaguti E, Mahjoub AR, Martin S. The vertex k -cut problem. Discrete Optimization. 2019;31:8-28. doi:10.1016/j.disopt.2018.07.003
BibTeX
@article{Cornaz2019,
author = {Cornaz, Denis and Furini, Fabio and Lacroix, Mathieu and Malaguti, Enrico and Mahjoub, A. Ridha and Martin, Sébastien},
title = {The vertex k -cut problem},
journal = {Discrete Optimization},
year = {2019},
volume = {31},
pages = {8--28},
doi = {10.1016/j.disopt.2018.07.003}
}
EUVIMED