Skip to Main content Skip to Navigation
Journal articles

Exact and heuristic methods for the vertex separator problem

Abstract : 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.
Complete list of metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02427906
Contributor : Mohamed Didi Biha <>
Submitted on : Saturday, January 4, 2020 - 3:29:47 PM
Last modification on : Monday, April 27, 2020 - 4:14:03 PM

Links full text

Identifiers

Collections

Citation

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

Share

Metrics

Record views

50