Accessibility Tools
Os Seminários PESC têm como objetivo trazer palestras acessíveis a um público mais amplo, ministradas por pesquisadores e professores mais experientes (tanto do PESC como de instituições externas). Ao longo do ano, teremos temas e focos variados, podendo ser mais específicos ou mais abrangentes.
A apresentação e discussão de ideias novas e antigas de diferentes temas contribui de maneira fundamental para a formação e pesquisa desenvolvida por alunos e professores, sendo muitas vezes de interesse de um público mais amplo.
Os Seminários que são on-line ou híbridos ficam gravados no Canal do PESC no YouTube, que apresenta muitas outras gravações importantes sobre o que acontece no PESC.
List matrix partition problems on chordal graphs parameterized by leafage
Flavia Bonomo (Universidad de Buenos Aires), Professora Associada
Moderador: Prof. Jayme Luiz Szwarcfiter
Dia 12/04 (quarta-feira), 10 horas, Sala H-324B.
Transmissão ao vivo no Canal do PESC no YouTube.
Cartaz
Abstract:
Graph k-coloring and k-clique cover are examples of partition problems in graphs, in the first case into k independent sets, in the second case into k cliques. Moreover, maximum clique and maximum independent set are examples of partition problems into two sets, one arbitrary and the other one required to be a clique (resp. independent set), with the addition of a linear objective function to maximize. These are examples of matrix partition problems. For each symmetric matrix M over {0,1,*}, the M-partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges joining them, or to have all edges joining them, as encoded in the matrix. Moreover, the vertices of the input graph can be equipped with lists, restricting the parts to which a vertex can be placed. Even if the first four problems (k-coloring, k-clique cover, maximum clique and maximum independent set) are polynomially solvable on chordal graphs, Feder, Hell, Klein, Nogueira and Protti in 2005 proved that there are M-partition problems (without lists) that remain NP-complete for chordal graphs. In this talk, making use of a graph width parameter called "thinness", we will show that all list matrix partition problems with linear objective functions are XP on chordal graphs, parameterized by the leafage of the chordal graph. (The leafage of a chordal graph is the minimum number of leaves in a tree such that the graph can be realized as an intersection graph of subtrees of that tree.)
These results are from joint works with Diego De Estrada and with Nick Brettell, Andrea Munaro and Daniël Paulusma.
Short Bio:
Flavia Bonomo é licenciada em Ciências Matemáticas e doutora em Ciências da Computação pela Universidade de Buenos Aires. Atualmente atua como Professora Associada com dedicação exclusiva no Departamento de Computação da FCEN-UBA e Pesquisadora do ICC-CONICET (Argentina). Sua principal área de pesquisa é a Teoria dos Grafos, embora também tenha artigos publicados sobre tópicos de Pesquisa Operacional, e mantém estreita colaboração nesses temas desde 2002 com pesquisadores da COPPE, UFRJ. No campo da Teoria dos Grafos seus principais tópicos de interesse cobrem as caracterizações estruturais de classes de grafos, o estudo de diferentes parâmetros de largura em grafos, e a delimitação de fronteiras em termos de complexidade computacional e classes de grafos para vários problemas de otimização combinatória.
.png)
.png)
