The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut

DOI10.1016/j.dam.2018.10.005zbMath1405.05143OpenAlexW2912091052WikidataQ128471434 ScholiaQ128471434MaRDI QIDQ1728091

Youcef Magnouche, Denis Cornaz, Ali Ridha Mahjoub, Sébastien Martin

Publication date: 21 February 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.10.005

zbMATH Keywords

complexityinteger programmingbranch-and-cut algorithmpolytopefacetseparation algorithmvertex separator problem

Mathematics Subject Classification ID

Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

The multi-terminal vertex separator problem: branch-and-cut-and-price ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem

Cites Work

• Unnamed Item
• An exact algorithm for solving the vertex separator problem
• On the hardness of approximating minimum vertex cover
• Parameterized graph separation problems
• Simple and improved parameterized algorithms for multiterminal cuts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• The vertex separator problem: algorithms and computations
• The vertex separator problem: a polyhedral investigation
• On the minimum cut separator problem
• Minimum-cost flow algorithms: an experimental evaluation
• The Complexity of Multiterminal Cuts
• A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices
• Partitioning a Graph into Small Pieces with Applications to Path Transversal
• Multiway cuts in directed and node weighted graphs
• Multiway cuts in node weighted graphs
• The k-Separator Problem

This page was built for publication: The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut