Particionamento conectado em grafos espaciais com objetivo bottleneck: formulação, calibração exata e refinamento heurístico

Este trabalho formaliza e avalia um problema de particionamento conectado em grafos espaciais de proximidade com número fixo de clusters. A tarefa consiste em dividir os vértices em k clusters conexos, maximizando uma utilidade bottleneck-cardinality na qual cada cluster contribui pela cardinalidade multiplicada pelo menor atributo de seus vértices. A avaliação combina um baseline exato de calibração em microinstâncias, formulado como set partitioning sobre subconjuntos conectados, e um benchmark pareado entre um construtor guloso e um refinador local que preserva conectividade. Nas microinstâncias n = 12, o modelo exato resolveu as 15 combinações semente-k testadas. No benchmark principal, com 30 execuções pareadas em instâncias de 100 e 500 vértices, o refinador superou o construtor em todos os pares, com ganho médio de 81.59 e teste de Wilcoxon unilateral significativo (p = 9.31 × 10^-10). Os resultados indicam ganhos sistemáticos, ao custo de maior tempo computacional.