Exact and heuristic methods for the vertex separator problem - Normandie Université Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

Exact and heuristic methods for the vertex separator problem

Haeder y Althoby
  • Fonction : Auteur
Mohamed Didi Biha

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.
Fichier principal
Vignette du fichier
Vertex-Separator-problem.pdf (307.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02156556 , version 1 (14-06-2019)

Identifiants

  • HAL Id : hal-02156556 , version 1

Citer

Haeder y Althoby, Mohamed Didi Biha, André Sesboüé. Exact and heuristic methods for the vertex separator problem. 2019. ⟨hal-02156556⟩
26 Consultations
696 Téléchargements

Partager

Gmail Facebook X LinkedIn More