The vertex \(k\)-cut problem
From MaRDI portal
Publication:2419357
DOI10.1016/j.disopt.2018.07.003zbMath1506.90255OpenAlexW2890368053WikidataQ57658998 ScholiaQ57658998MaRDI QIDQ2419357
Sébastien Martin, Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, Ali Ridha Mahjoub
Publication date: 13 June 2019
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2018.07.003
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Mixed integer programming (90C11) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A branch-and-price algorithm for capacitated hypergraph vertex separation, LP-based dual bounds for the maximum quasi-clique problem, Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem, On integer and bilevel formulations for the \(k\)-vertex cut problem, A compact mixed integer linear formulation for safe set problems, Political districting to minimize cut edges
Uses Software
Cites Work
- Unnamed Item
- An exact algorithm for solving the vertex separator problem
- Parameterized graph separation problems
- Finding good approximate vertex and edge partitions is NP-hard
- Plant location with minimum inventory
- Minimum 0-extensions of graph metrics
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the \(k\)-cut problem
- The vertex separator problem: algorithms and computations
- The vertex separator problem: a polyhedral investigation
- Branch-and-Price: Column Generation for Solving Huge Integer Programs
- On Multiway Cut Parameterized above Lower Bounds
- On the minimum cut separator problem
- A new approach to the maximum-flow problem
- On the multiway cut polyhedron
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- An $\NC$ Algorithm for Minimum Cuts
- Multiway cuts in directed and node weighted graphs
- Complexity and approximability of the k‐way vertex cut
- Multiway cuts in node weighted graphs
- The k-Separator Problem
- NP-completeness of the Planar Separator Problems
- Column Generation
- Discrete convexity and polynomial solvability in minimum 0-extension problems