The vertex separator problem: a polyhedral investigation

DOI10.1007/s10107-005-0574-7zbMath1099.90065OpenAlexW2015635922MaRDI QIDQ2487852

Egon Balas, Cid Carvalho De Souza

Publication date: 8 August 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0574-7

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

The multi-terminal vertex separator problem: branch-and-cut-and-price ⋮ On the minimum cut separator problem ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ A quality and distance guided hybrid algorithm for the vertex separator problem ⋮ A branch-and-price algorithm for capacitated hypergraph vertex separation ⋮ The vertex \(k\)-cut problem ⋮ Approximating polyhedra with sparse inequalities ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ An exact algorithm for solving the vertex separator problem ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ A compact mixed integer linear formulation for safe set problems ⋮ Knowledge Discovery in Graphs Through Vertex Separation ⋮ Exact algorithms for the vertex separator problem in graphs ⋮ The MIN-cut and vertex separator problem ⋮ The critical node detection problem in networks: a survey ⋮ A hybrid breakout local search and reinforcement learning approach to the vertex separator problem ⋮ Optimizing over the split closure ⋮ Disconnecting graphs by removing vertices: a polyhedral approach ⋮ The vertex separator problem: algorithms and computations ⋮ Unnamed Item ⋮ The Multi-terminal Vertex Separator Problem: Polytope Characterization and TDI-ness ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

• Unnamed Item
• Unnamed Item
• Partitioning planar graphs with vertex costs: Algorithms and applications
• The vertex separator problem: algorithms and computations
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Parallel Algorithms for Sparse Linear Systems
• Finding Separator Cuts in Planar Graphs within Twice the Optimal
• Geometric Separators for Finite-Element Meshes