An exact algorithm for solving the vertex separator problem

DOI10.1007/s10898-010-9568-yzbMath1211.90260OpenAlexW1967802975MaRDI QIDQ628743

Mohamed Didi Biha, Marie-Jean Meurs

Publication date: 14 March 2011

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-010-9568-y

zbMATH Keywords

graph partitioningvertex separatorpolyhedral approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

The multi-terminal vertex separator problem: branch-and-cut-and-price ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ A quality and distance guided hybrid algorithm for the vertex separator problem ⋮ General variable neighborhood search for computing graph separators ⋮ The vertex \(k\)-cut problem ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ Knowledge Discovery in Graphs Through Vertex Separation ⋮ 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 ⋮ A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem ⋮ The Multi-terminal Vertex Separator Problem: Polytope Characterization and TDI-ness

Cites Work

• Finding good approximate vertex and edge partitions is NP-hard
• On implementing the push-relabel method for the maximum flow problem
• The vertex separator problem: algorithms and computations
• The vertex separator problem: a polyhedral investigation
• A Separator Theorem for Planar Graphs
• NP-completeness of the Planar Separator Problems
• Algorithms and Computation