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

               Tarde de Teoria do Grafos
============================================================

Título:      On the Structure of Trees with Large Minimum 
             Bisection Width
            
Palestrante: Tina Janne Schmidt
             Technische Universität München

Hora e Data: 15h15m, sexta-feira, 06 de dezembro de 2013

Local:       Sala Multi-usos do Numec

Resumo:

A bisection of a graph is a partition of its vertex set into
two sets, called white and  black set, of sizes differing by
at most one.  The width of a bisection  counts the number of
edges between  the white and  the black set.   Determining a
bisection  of minimum  width is  NP-hard. It  is  known that
bounded  degree trees  on n  vertices allow  a  bisection of
width O(log  n). We investigate  the structure of  trees for
which this bound is tight up to a constant factor by showing
a bound on the length of  the paths in such trees. To do so,
an inequality relating the width of a minimum bisection with
the diameter of a tree is  used. We will sketch the proof of
a special case of  this inequality, which implies that every
bounded degree tree on n vertices with diameter at least n/4
allows a bisection of constant width.