Todos são bem-vindos!!
Seminário de Algoritmos e Combinatória
Título: Partição de Árvores em Subárvores balanceadas
Palestrante: Renato Lucindo
Local: sala 6 do bloco B
Data: terça, 20 de setembro, às 13:00
Resumo:
Seja q um inteiro maior que 1. O problema Max q-Partição Conexa Balanceada (Max-PCB$_q$) é o seguinte: dados um grafo G = (V,E) conexo e uma função peso $w: V \rightarrow Z$ definida sobre seus vértices, encontrar uma q-partição (V_{1}, V_{2}, ...,V_{q}) de V tal que G[V_i] é conexo ( i=1, ..., q) e maximiza a função min{w(V_i): i = 1, ..., q} (onde w(S) denota o peso do conjunto S). Este problema é NP-difícil no sentido forte para grafos quaisquer. Mostraremos um algoritmo polinomial que resolve o caso particular em que o grafo G é acíclico.
Fórum