O grupo de Grafos e Algoritmos da UFRJ convida a todos para o seminário a ser realizado em 15/06/2016, quarta-feira próxima.

Local - Coppe/Sistemas

Sala - H-324B

Horario - 10:30h

Palestrante:

Fabiano de Souza Oliveira, Professor

Título:

O problema da contagem de intervalos: uma atualização

Resumo:

Um grafo é um grafo de intervalo se é o grafo de interseção de uma família de intervalos da reta real. Há inúmeros trabalhos na literatura sobre muitos aspectos dos grafos de intervalo. Na década de 80, já havia um livro inteiramente dedicado a problemas nesta classe de grafos, intitulado *Interval Graphs and Interval Orders*, por P. Fishburn.

Apesar de formar uma classe de grafos bem-conhecida e bem-estudada, sabe-se muito pouco à respeito do problema de otimização que surge de forma natural a partir da definição de tal classe, a saber: dado um grafo de intervalo de entrada, determinar o número de tamanhos de intervalo que é necessário e suficiente para se representar um modelo de G. Se tal número mínimo é k, dizemos que G possui interval count k. O primeiro interesse ao problema é atribuído a R. Graham.

Reconhecer se um dado grafo G possui interval count igual a 1 é equivalente portanto a reconhecer se G admite um modelo com um único tamanho de intervalo, o que ocorre precisamente se G for de intervalo unitário, problema bem-resolvido. Pouco se sabe no entanto acerca da complexidade de reconhecer se um grafo possui interval count k >= 2, mesmo para k fixo. Até recentemente, a grande maioria dos resultados sobre o problema constavam no livro de Fishburn. Porém, alguns resultados relativamente recentes surgiram. Neste seminário, apresentarei resultados antigos e recém publicados sobre o assunto.

Observações:

Fabiano fez seu doutorado no PESC/COPPE sob orientação dos professores Jayme Szwarcfiter e Márcia Cerioli e é atualmente professor no IME/UERJ.

Consulte também a página de seminários do Grupo.