Algorithms for Balanced Connected Partitions of Graphs

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximaçãoIn this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm