============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      An Effective Upperbound on Treewidth Using Partial 
             Fill-in of Separators
            
Palestrante: Martin Charles Golumbic 
             University of Haifa

Hora e Data: 14h00, sexta-feira, 18 de dezembro de 2009

Local:       auditório do NUMEC

Resumo:

Partitioning   a   graph   using   graph   separators,   and
particularly clique separators, are well-known techniques to
decompose a  graph into smaller  units which can  be treated
independently.  It  was previously known  that the treewidth
was bounded  above by the sum  of the size  of the separator
plus  the treewidth  of  disjoint components,  and this  was
obtained by  the heuristic  of filling in  all edges  of the
separator making it into a clique.

In this paper, we present  a new, tighter upper bound on the
treewidth of  a graph obtained by only  partially filling in
the  edges  of  a   separator.  In  particular,  the  method
completes just  those pairs  of separator vertices  that are
adjacent  to  a  common  component,  and  indicates  a  more
effective heuristic than filling in the entire separator.

We discuss  the relevance  of this result  for combinatorial
algorithms and give an example  of how the tighter bound can
be  exploited  in  the  domain  of  constraint  satisfaction
problems.

Joint work with Boi Faltings.