EUVIMEDEUVIMED entdecken
Crossref

The vertex k -cut problem

Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, A. Ridha Mahjoub, Sébastien Martin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →