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 条

[31] A Balanced Vertex Cut Partition Method in Distributed Graph Computing
Sun, Rujun
Zhang, Lufei
Chen, Zuoning
Hao, Ziyu
INTELLIGENCE SCIENCE AND BIG DATA ENGINEERING: BIG DATA AND MACHINE LEARNING TECHNIQUES, ISCIDE 2015, PT II, 2015, 9243 : 43 - 54
[32] New Mathematical Model for Finding Minimum Vertex Cut Set
Sevim, Tina Beseri
Kutucu, Hakan
Berberler, Murat Ersen
2012 IV INTERNATIONAL CONFERENCE PROBLEMS OF CYBERNETICS AND INFORMATICS (PCI), 2012,
[33] Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths Problem
Ruangwises, Suthee
Itoh, Toshiya
NEW GENERATION COMPUTING, 2021, 39 (01) : 3 - 17
[34] An Exact Algorithm for Finding k-Biclique Vertex Partitions of Bipartites
Liu, Peiqiang
2012 2ND INTERNATIONAL CONFERENCE ON APPLIED ROBOTICS FOR THE POWER INDUSTRY (CARPI), 2012, : 553 - 556
[35] SBV-Cut: Vertex-cut based graph partitioning using structural balance vertices
Kim, Mijung
Candan, K. Selcuk
DATA & KNOWLEDGE ENGINEERING, 2012, 72 : 285 - 303
[36] Informational Entropy of B-ary Trees after a Vertex Cut
Jaentschi, Lorentz
Bolboaca, Sorana D.
ENTROPY, 2008, 10 (04) : 576 - 588
[37] A vertex cut algorithm for model order reduction of parasitic resistive networks
Kitanov, Petko
Marcotte, Odile
Schilders, Wil H. A.
Shontz, Suzanne M.
COMPEL-THE INTERNATIONAL JOURNAL FOR COMPUTATION AND MATHEMATICS IN ELECTRICAL AND ELECTRONIC ENGINEERING, 2012, 31 (06) : 1850 - 1871
[38] Vertex cut, eigenvalues, [a, b]-factors and toughness of connected bipartite graphs
Hao, Yifang
Li, Shuchao
Li, Xuechao
DISCRETE MATHEMATICS, 2024, 347 (10)
[39] ON COHOMOLOGY OF QUASITORIC MANIFOLDS OVER A VERTEX CUT OF A FINITE PRODUCT OF SIMPLICES
Sarkar, Soumen
Sau, Subhankar
MOSCOW MATHEMATICAL JOURNAL, 2024, 24 (02) : 287 - 315
[40] The generalized vertex cover problem and some variations
Pandey, Pooja
Punnen, Abraham P.
DISCRETE OPTIMIZATION, 2018, 30 : 121 - 143

← 1 2 3 4 5 →