Recent algorithmic results on equitable coloring

Speaker: Vinicius Santos, UFMG.

Date: 18 dec 2019, 11h.

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

Abstract: A proper coloring of a graph is a labeling of its vertex set such that adjacent vertices receive distinct labels. Many problems can be modelled using graph colorings, such as scheduling and task assignment problems. On such problems, one may be interested in the case where the coloring is balanced in the following sense: the number of times two different colors occurs in the graph can differ by at most one. Such proper colorings are called equitable colorings.

Similarly to the traditional version, determining whether a graph has an equitable coloring with a given amount of colors is a computationally hard problem. However, for many settings where coloring is tractable, the problem becomes hard for the equitable version. In this talk we present some recent advances on this problem, such as polynomial time algorithms for some special cases and positive and negative results concerning the parameterized complexity of the problem.

This is joint work with Matheus Guedes and Guilherme Gomes.

 

Introdução sobre complexidade parametrizada e problemas

Speakers: Ignasi Sau, LIRMM; Ueverton Souza, IC-UFF.

Date: 27 nov 2019, 13h.

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

Abstract: Nesta palestra faremos uma breve introdução sobre algoritmos e complexidade parametrizada, uma das áreas mais promissoras da teoria da computação. Em seguida serão apresentados alguns problemas de nosso interesse particular tais como deleção de vértices em grafos com bounded treewidth para obtenção de estruturas livres de certos subgrafos induzidos. Em especial abordaremos o desenvolvimento de algoritmos de tempo single-exponencial com relação a treewidth do grafo de entrada para resolução problemas como deleção de vértices para obtenção de grafos livres de conjuntos independentes induzidos de tamanho k.

 

Jogo Mapa do Tesouro

Speaker: Andressa Martins Moraes, UFRJ/PPGI/AMN.

Date: 30 sep 2019, 13h.

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

Abstract: Neste seminário apresentarei o Jogo Mapa do Tesouro, um jogo em grafos aplicado na educação com objetivo de avaliar o desenvolvimento da aprendizagem utilizando conceitos da neurociência e empregando uma estrutura baseada em grafos.

 

The size-Ramsey number of powers of bounded degree trees

Speaker: Taísa Martins, IMPA.

Date: 28 aug 2019, 13h.

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

Abstract: Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges where in any s-colouring of E(G) there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex tree is linear on n.

This is a joint work with S. Berger, Y. Kohayakawa, G. S. Maesaka, W. Mendonça, G. O. Mota and O. Parczyk.

 

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.

 

Pagina 1 de 2