The vertex \(k\)-cut problem

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

zbMATH Keywords

exact algorithmsbranch and pricemixed-integer programming modelsvertex cut

Mathematics Subject Classification ID

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

• DIMACS

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