Esta semana temos uma dobradinha no Ciclo de Seminários PESC, nesta quarta, às 11h, com as professoras Cláudia Sales (UFC) e Ana Shirley (UFC), irão apresentar um resumo de seus muitos trabalhos em coloração de grafos - um dos problemas clássicos da computação. Este é um daqueles problemas que na teoria é difícil (NP-Completo desde os anos 1970) mas que na prática vem sendo resolvido de forma bem satisfatória, seja de forma aproximada ou em contextos mais restritos. Paradoxos como este vem impulsionando a computação a buscar por novas teorias para melhor enquadrar o difícil e o fácil, a "complexidade prática" como disse Moshe Vardi (link).

Programe-se, participe e ajude na divulgação! 

Mais detalhes abaixo ou clicando aqui.

-------------------------------

Palestrantes:

Cláudia Linhares Sales, Professora Titular, Universidade Federal do Ceará (UFC)

Ana Shirley F. da Silva, Professora Adjunta, Universidade Federal do Ceará (UFC)

Título:

Even if it's hard, keep coloring

Dia/horário/local:

14 de novembro (quarta), 11h, sala H-324B

Resumo:

In this seminar, we are going to summarize our joint work with Frédéric Maffray, separately and together. It was almost all about colorings, looking for methods to exactly color graphs or find classes of graphs which could be easily colored, and by the end, measuring the quality of easy methods to color them.

Cláudia is going to talk mainly about "paires d'amis" (couple of friends or even pair) as their main results were about friendship, explaining how "paires d'amis" can be used to color graphs. She is going to remember their search for "pair d'amis" in planar graphs, claw-free graphs, dart-free graphs and C_4-free graphs, and how they turn their search to mesure the quality of the greedy and b-heuristics colorings, already together with Ana.

Ana is going to talk about her work on b-colorings, started with Frédéric Maffray and continued with other co-authors. In particular, she is going to talk about the b-chromatic number and the b-continuity of graphs with large girth. These concepts were introduced in 1999, by Irving and Manlove, in the light of an heuristic that tries to decrease the number of colors used in a given proper coloring of the graph, called b-heuristic.

Biografia resumida:

Cláudia Linhares Sales é professora titular da Universidade Federal do Ceará e ocupou o cargo de Diretora Científica da FUNCAP (Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico) em 2010-2011 e 2012-2014. Possui mestrado em Engenharia de Sistemas e Computação pela Universidade Federal do Rio de Janeiro (1990) e doutorado em Informatique - Recherche Operationnelle - Université de Grenoble I (Scientifique Et Medicale - Joseph Fourier) (1996), sob a supervisão de Frédéric Maffray. Fez pós-doutorado no INRIA/Sophia-Antipolis, França, entre 2006 e 2007, e na Simon Fraser University, Canadá, entre 2015 e 2016. Trabalha com Teoria dos Grafos e Algoritmos, atuando principalmente nos temas de coloração e decomposição de grafos.

Ana Shirley F. da Silva é professora no Departamento de Matemática da Universidade Federal do Ceará. Ela obteve seu título de doutora em 2010 também sob a supervisão de Frédéric Maffray na Université de Grenoble, França, e passou um ano com bolsa de pós-doutorado no Centrum Wiskunde & Informatica, Amsterdã, entre 2015 e 2016. Ela é bolsista de produtividade nível 2 e trabalha principalmente com problemas de coloração em grafos.

Ambas as professores são membros do grupo de pesquisa ParGO (Paralelismo, Grafos e Otimização), sendo a Prof. Cláudia membro fundadora do grupo.