On integer and bilevel formulations for the \(k\)-vertex cut problem

DOI10.1007/s12532-019-00167-1zbMath1447.90011OpenAlexW2964998526MaRDI QIDQ2195678

Paolo Paronuzzi, Ivana Ljubić, Enrico Malaguti, Fabio Furini

Publication date: 27 August 2020

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-019-00167-1

zbMATH Keywords

branch-and-cut algorithminteger linear programmingbilevel programmingvertex cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Critical node/edge detection problems on trees, Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem, A branch-and-cut algorithm for the connected max-\(k\)-cut problem, Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem, A survey on mixed-integer programming techniques in bilevel optimization, Models and algorithms for the weighted safe set problem, An exact method for binary fortification games, Mathematical programming formulations for the collapsed k-core problem, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, Political districting to minimize cut edges

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Parameterized graph separation problems
• Finding good approximate vertex and edge partitions is NP-hard
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• The maximum clique interdiction problem
• The critical node detection problem in networks: a survey
• On the \(k\)-cut problem
• A branch-and-price algorithm for capacitated hypergraph vertex separation
• The vertex \(k\)-cut problem
• The vertex separator problem: algorithms and computations
• The vertex separator problem: a polyhedral investigation
• On the minimum cut separator problem
• On the multiway cut polyhedron
• Decomposing Matrices into Blocks
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• 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
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• NP-completeness of the Planar Separator Problems
• Automata, Languages and Programming
• Benchmarking optimization software with performance profiles.