An exact algorithm for solving the vertex separator problem |
| |
Authors: | Mohamed Didi Biha Marie-Jean Meurs |
| |
Institution: | 1.Laboratoire d’Analyse Non linéaire et Géométrie (EA 2151),Université d’Avignon et des Pays de Vaucluse,Avignon,France;2.LMNO, Université de Caen,Caen Cedex,France;3.Laboratoire Informatique d’Avignon (EA 931),Université d’Avignon et des Pays de Vaucluse,Avignon,France |
| |
Abstract: | Given G = (V, E) a connected undirected graph and a positive integer β(|V|), the vertex separator problem is to find a partition of V into no-empty three classes A, B, C such that there is no edge between A and B, max{|A|, |B|} ≤ β(|V|) and |C| is minimum. In this paper we consider the vertex separator problem from a polyhedral point of view. We introduce new classes
of valid inequalities for the associated polyhedron. Using a natural lower bound for the optimal solution, we present successful
computational experiments. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|