Exact and heuristic methods for the vertex separator problem - Normandie Université Accéder directement au contenu
Article Dans Une Revue Computers & Industrial Engineering Année : 2020

Exact and heuristic methods for the vertex separator problem

Résumé

In this paper, we propose a practical and efficient methods to solve the vertex separator problem (VSP for short), based on branch-and-bound procedure, which uses linear programming, and a greedy algorithm. This problem arises in many areas of applications such as graph algorithms, communication networks, solving systems of equations, finite element and finite difference problems. We show, by computational experiments, that our approach is able to solve in short time large-scale instances of VSP from the literature to optimality or near optimality.
Fichier principal
Vignette du fichier
S0360835219306047.pdf (371.14 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02427906 , version 1 (20-07-2022)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Haeder Althoby, Mohamed Didi Biha, André Sesboüé. Exact and heuristic methods for the vertex separator problem. Computers & Industrial Engineering, 2020, 139, pp.106135. ⟨10.1016/j.cie.2019.106135⟩. ⟨hal-02427906⟩
41 Consultations
33 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More