Partições Conexas Balanceadas de Grafos

Abstract

O avanço tecnológico tem contribuído para uma sociedade cada vez mais conectada, proporcionando uma melhora na qualidade de vida nos mais diversos aspectos. Para tratar problemas como, por exemplo, sobre conjuntos de objetos que exibem propriedades que se traduzem em relações binárias entre eles, e nos quais se objetiva descobrir a existência de certas subestruturas e/ou otimizar alguma função, em especial os de natureza discreta, os grafos podem ser as estruturas matemáticas apropriadas. Problemas de partições balanceadas podem ser aplicados nesse contexto, no sentido que o grafo de entrada pode ter pesos associados aos seus vértices e o balanceamento deve levar em conta o peso dos subgrafos conexos da partição. Ao precisar esse conceito de balanceamento, obtemos algumas variantes do problema. Logo, o foco deste artigo é um problema dessa natureza, que chamamos de Problema da Partição Conexa Balanceada (PCB). Ao longo do estudo, os experimentos computacionais conduzidos mostraram que os algoritmos exatos implementados têm desempenho substancialmente melhores que os métodos exatos publicados na literatura. Adicionalmente, obtivemos os primeiros resultados poliédricos associados à segunda formulação restrita ao caso de pesos uniformes. Tais resultados podem levar a novas abordagens para o PCBk.