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

  1. How to cite this page
  2. Problem definition
  3. Instance files
  4. Published Results
  5. References

How to cite this page

Problem definition

top

Instance files

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

 

top

Published Results

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

 

top


References

  • 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.
    top


    Copyright: 2005, IC/UNICAMP, All Rights Reserved.
    Last update: 08/03/08, by Cid C. de Souza.