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

DOI10.1016/J.DAM.2018.10.005MaRDI QIDQ1728091zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

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

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)