Exact and heuristic methods for the vertex separator problem
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...