Partição de um grafo em subgrafos conexos balanceados

Resumo:

Seja G=(V,E) um grafo conexo com uma função peso w: V -> Z⁺ e q um inteiro positivo, q >= 2. Se X é um subconjunto de vértices, denotamos por w(X) a soma dos pesos dos vértices em X. O problema da q-partitição conexa balanceada consiste em encontrar uma q -partição P=(V₁,V₂, ..., V_q) de V tal que G[V_i] é conexo (1 <= i <= q) e P maximiza min {w(V_i): 1 <= i <= q}. O papel desta função objetivo é obter subgrafos conexos de pesos balanceados. Este problema é NP-difícil mesmo para grafos planares. Apresentamos resultados de inaproximabilidade e algoritmos de aproximação para este problema.