Proposta de dissertação do MEI Título: Divisões mínimas em grafos Proponente(s): Margarida Mamede Créditos: 42 ECTS Área científica: Software Construction and Analysis Início preferencial: 1º Semestre URL: Já estão em curso trabalhos preliminares executados pelo alunos: Breve descrição: Assumindo que os dados de uma computação estão localizados em vários sítios, que os resultados são colocados noutro sítio e que os cálculos intermédios podem ser realizados em qualquer dos sítios anteriormente referidos, o problema de determinar onde devem ser efetuados os cálculos intermédios, de forma a minimizar a quantidade de informação transferida entre sítios diferentes, pode ser reduzido a uma variante do problema do corte-k mínimo, denominada problema do corte-k mínimo com vértices especiais. Num trabalho anterior, desenvolveu-se um algoritmo para o problema do corte-k mínimo com vértices especiais. Neste trabalho, pretende-se colocar a hipótese de ter alguns dados replicados em vários sítios e verificar se isso permite reduzir a quantidade de informação transferida entre sítios diferentes. Observações: Este tema está atribuído à aluna Raissa Almeida