Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Exact and heuristic methods for the vertex separator problem

Abstract : Given a connected undirected graph G = (V, E) with n vertices and a positive integer β(n), the vertex separator problem (VSP for short) is to find a partition of V into nonempty three classes A, B, C such that there is no edge between A and B, max{|A|, |B|} ≤ β(n) and |C| is minimum. In this paper, we propose a pratical and efficient methods to solve VSP, based on branch-and-bound procedure, which uses linear programming, and a greedy algorithm. We show, by computational experiments , that our approach is able to solve in short time large-scale instances from the literature to optimality or near optimality.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Mohamed Didi Biha Connect in order to contact the contributor
Submitted on : Friday, June 14, 2019 - 2:32:48 PM
Last modification on : Wednesday, November 3, 2021 - 6:17:54 AM


Files produced by the author(s)


  • HAL Id : hal-02156556, version 1



Haeder Althoby, Mohamed Biha, André Sesboüé. Exact and heuristic methods for the vertex separator problem. 2019. ⟨hal-02156556⟩



Les métriques sont temporairement indisponibles