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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02156556
Contributor : Mohamed Didi Biha <>
Submitted on : Friday, June 14, 2019 - 2:32:48 PM
Last modification on : Monday, April 27, 2020 - 4:14:03 PM

File

Vertex-Separator-problem.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02156556, version 1

Collections

Citation

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

Share

Metrics

Record views

38

Files downloads

148