Data: 22/04/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Partição de grafos em subgrafos conexos e balanceados
Palestrante: Phablo Moura (UFMG)


Resumo: O problema de Particionamento Conexo Balanceado (PCB) consiste em particionar o conjunto de vértices de um grafo ponderado de forma que cada classe dessa partição induz um subgrafo conexo e as classes possuem pesos similares. Mais formalmente, dados um grafo conexo G com pesos positivos associados aos seus vértices e um inteiro positivo k, o objetivo no PCB é encontrar uma partição {V_1, ..., V_k} de V(G) tal que G[V_i] é conexo para cada i \in {1,...,k} e o peso da classe mais leve é máximo. Neste seminário, investigaremos tal problema do ponto de vista de algoritmos de aproximação e programação linear inteira.