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

DOI10.1016/J.DAM.2018.10.005zbMATH Open1405.05143OpenAlexW2912091052WikidataQ128471434 ScholiaQ128471434MaRDI QIDQ1728091FDOQ1728091

Authors: Denis Cornaz, Youcef Magnouche, A. R. 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

Recommendations

• The multi-terminal vertex separator problem: branch-and-cut-and-price
• The multi-terminal vertex separator problem: polytope characterization and TDI-ness
• The vertex separator problem: a polyhedral investigation
• An exact algorithm for solving the vertex separator problem
• The vertex separator problem: algorithms and computations

zbMATH Keywords

complexityinteger programmingpolytopefacetbranch-and-cut algorithmseparation algorithmvertex separator problem

Mathematics Subject Classification ID

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

Cites Work

• Minimum-cost flow algorithms: an experimental evaluation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the minimum cut separator problem
• The Complexity of Multiterminal Cuts
• Multiway cuts in node weighted graphs
• On the hardness of approximating minimum vertex cover
• Parameterized graph separation problems
• The vertex separator problem: a polyhedral investigation
• The vertex separator problem: algorithms and computations
• Title not available (Why is that?)
• Simple and improved parameterized algorithms for multiterminal cuts
• Multiway cuts in directed and node weighted graphs
• The \(k\)-separator problem
• A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices
• An exact algorithm for solving the vertex separator problem
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• Partitioning a graph into small pieces with applications to path transversal

Cited In (13)

• Integer programming models and polyhedral study for the geodesic classification problem on graphs
• The multi-terminal vertex separator problem: branch-and-cut-and-price
• Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
• The multi-terminal vertex separator problem: polytope characterization and TDI-ness
• A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem
• A branch-and-price algorithm for capacitated hypergraph vertex separation
• 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
• A multivariate analysis of the strict terminal connection problem
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• An exact algorithm for solving the vertex separator problem
• The vertex separator problem: a polyhedral investigation
• A note on the SDP relaxation of the minimum cut problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1728091)