Name
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.disopt.2018.07.003 | Discrete Optimization |
Keywords | Field | DocType |
Vertex cut,Mixed-integer programming models,Branch and Price,Exact algorithms | Integer,Discrete mathematics,Graph,Column generation,Vertex (geometry),Cardinality,Mathematics,Branching (version control) | Journal |
Volume | ISSN | Citations |
31 | 1572-5286 | 0 |
PageRank | References | Authors |
0.34 | 17 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| denis cornaz | 1 | 1 | 1.37 |
| Fabio Furini | 2 | 104 | 16.85 |
| Mathieu Lacroix | 3 | 19 | 7.23 |
| Enrico Malaguti | 4 | 312 | 21.69 |
| Ali Ridha Mahjoub | 5 | 2 | 4.17 |
| Sébastien Martin | 6 | 11 | 2.96 |