Instances for the Vertex Separator Problem (VSP) (by V. F. Cavalcante and C. C. de Souza)

**How to cite this page**
**Problem definition**
**Instance files**
**Published Results**
**References**

Please use the BibTeX entry below:

`
@Misc{vsp-instances-page,`

author = {V. F. Cavalcante and C. C. de Souza},

title = {Test Instances for the Vertex Separator Problem ({VSP})},

howpublished = {{\tt www.ic.unicamp.br/\raisebox{-0.6ex}{\~{ }}cid/Problem-instances/VSP.html}},

}

There are 142 data files corresponding to VSP test instances available
here
All of these instances are solved in
"The vertex separator problem:
algorithms and computations"
(see reference details in References
section).
The format of these data files is:

b value, number of nodes (n), number of edges

for each node i (i = 1,...,n) in turn:
'v', node, node cost

for each edge (i,j) (i,j=1,...,n, i < j) in turn:
'e', i, j, edge cost

The results presented just below were extracted from the paper "The vertex separator problem:
algorithms and computations" (see References
section).

###

**top**

E. Balas and C. C. de Souza, The vertex separator problem: a
polyhedral investigation. **Mathematical Programming - Series A**, Volume
103, Issue 3, Jul 2005, Pages 583 - 608.
C.C. de Souza and E. Balas, The vertex separator problem:
algorithms and computations. **Mathematical Programming - Series A**, Volume
103, Issue 3, Jul 2005, Pages 609 - 631.
V. F. Cavalcante and C.C. de Souza,
Lagrangian relaxation and cutting planes for the vertex separator problem.
**Lecture Notes in Computer Science**, vol. 4614, 471-482.
(Post) Proceedings of the First International Symposium on Combinatorics,
Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007),
Hangzhou, China, April 2007.

#####
© Copyright: 2005, IC/UNICAMP, All Rights Reserved.

##### Last update:
08/03/08,
by Cid C. de Souza.