The vertex k-cut problem

被引：12

作者：

Cornaz, Denis ^{[1
]}

Furini, Fabio ^{[1
]}

Lacroix, Mathieu ^{[2
]}

Malaguti, Enrico ^{[3
]}

Mahjoub, A. Ridha ^{[1
]}

Martin, Sebastien ^{[4
]}

机构：

[1] Univ Paris 09, PSL, CNRS, LAMSADE UMR 7243, F-75775 Paris 16, France

[2] Univ Paris 13, Sorbonne Paris Cite, LIPN, CNRS,UMR 7030, Ave JB Clement, F-93430 Villetaneuse, France

[3] Univ Bologna, DEI, Viale Risorgimento 2, I-40136 Bologna, Italy

[4] Univ Lorraine, LCOMS, F-57045 Metz, France

来源：

DISCRETE OPTIMIZATION | 2019年 / 31卷

关键词：

Vertex cut; Mixed-integer programming models; Branch and Price; Exact algorithms; SEPARATOR PROBLEM; ALGORITHM; COMPLEXITY;

D O I：

10.1016/j.disopt.2018.07.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：8 / 28

页数：21

共 50 条

[21] An exact approach for the Vertex Coloring Problem
Malaguti, Enrico
Monaci, Michele
Toth, Paolo
DISCRETE OPTIMIZATION, 2011, 8 (02) : 174 - 190
[22] The Multi-terminal vertex separator problem: Extended formulations and Branch-and-Cut-and-Price
Magnouche, Youcef
Mahjoub, A. Ridha
Martin, Sebastien
2016 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), 2016, : 683 - 688
[23] The K-partitioning problem: Formulations and branch-and-cut
Ales, Zacharie
Knippel, Arnaud
NETWORKS, 2020, 76 (03) : 323 - 349
[24] Distributed Vertex-Cut Partitioning
Rahimian, Fatemeh
Payberah, Amir H.
Girdzijauskas, Sarunas
Haridi, Seif
DISTRIBUTED APPLICATIONS AND INTEROPERABLE SYSTEMS (DAIS 2014), 2014, 8460 : 186 - 200
[25] A 5k-vertex kernel for 3-path vertex cover
Xiao, Mingyu
Kou, Shaowei
THEORETICAL COMPUTER SCIENCE, 2023, 959
[26] Finding a Small Vertex Cut on Distributed Networks
Jiang, Yonggang
Mukhopadhyay, Sagnik
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 1791 - 1801
[27] MINIMUM VIOLATION VERTEX MAPS AND THEIR APPLICATIONS TO CUT PROBLEMS
Kawarabayashi, Ken-ichi
Xu, Chao
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (04) : 2183 - 2207
[28] Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
Januschowski, Tim
Pfetsch, Marc E.
INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS, 2011, 6697 : 99 - 116
[29] On the complexity of the balanced vertex ordering problem
Kara, Jan
Kratochvil, Jan
Wood, David R.
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2007, 9 (01) : 193 - 202
[30] A NEW APPROACH TO THE VERTEX COLORING PROBLEM
Torkestani, Javad Akbari
CYBERNETICS AND SYSTEMS, 2013, 44 (05) : 444 - 466

← 1 2 3 4 5 →