@techreport{TR-IC-09-09,
  number = {IC-09-09},
  author = {Victor F. Cavalcante and Cid C. de Souza},
  title = {Hybrid {L}agrangian algorithms for optimal vertex
                  separators},
  month = {March},
  year = {2009}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 39 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      In this  paper we propose  a Lagrangian relaxation  framework to
      solve  the vertex  separator problem  (VSP).  This  framework is
      based on the development of relax-and-cut algorithms which embed
      the  separation  of valid  inequalities  for  the VSP  discussed
      in~[3]   in  the   subgradient   method.   These   relax-and-cut
      algorithms are  then used as  a preprocessing phase in  a hybrid
      algorithm  which combines  them  with branch-and-cut  algorithms
      proposed  in~[12].   This  is  done  basically  by  feeding  the
      branch-and-cut  algorithms not  only with  the primal  bound but
      also  the   cuts  separated  during   the  preprocessing  phase.
      Computational   results  obtained   with  benchmarks   from  the
      literature  showed  that  the  hybrid algorithm  developed  here
      outperforms the  best exact algorithm  available for the  VSP to
      date.
  }
}