Dificuldade e Eficiência de Problemas em Grafos, Strings e Permutações

Speaker: Luis Felipe Ignácio Cunha, IME-UFF.

Date: 21 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário, trataremos de problemas em grafos, strings e permutações. Estes problemas são desafiadores do ponto de vista combinatório e possuem muitas questões intrigantes há anos. Apresentaremos nosso avanços nos estudos abaixo.

-- Admissibilidade: desejamos obter num grafo G o menor inteiro t, tal que exista uma árvore geradora T cuja distância em T entre cada par de vértices vizinhos de G seja no máximo t;
-- Tesselabilidade: uma tesselação de um grafo G é uma partição do conjunto de vértices em cliques. Desejamos obter o menor t, tal que existam t tesselações cuja união das tesselações cubra o conjunto das arestas do grafo;
-- Blocos haplótipos: dadas k strings binárias, desejamos obter todas subsequências maximais cujos elementos em cada coluna sejam iguais.
-- Indexação de strings: desejamos preprocessar uma string binária de modo a responder em tempo constante se há uma substring de tamanho k com i cópias de 1s, para valores arbitrários de k e i;
-- Distância, Diâmetro, Centralidade, Mediana e Convexidade em permutações: estes são problemas associados a grupos simétricos de permutações, que possuem muitas aplicações em biologia matemática, cujo intuito é compreender melhor a filogenia de espécies.
Além de estudos obtidos nesses temas, serão apresentadas as colaborações em pesquisa e atividades de ensino e extensão em desenvolvimento.