Efficient Algorithms for the Capacity and Connectivity Graph Partition Problem

Abstract

This paper proposes some algorithms for the resolution of a real capacity and connectivity graph partition problem. A review of literature showing that the algorithms work only with the edges of the Minimum Spanning Tree is presented. In this case, the algorithms act on the original graph, in order to increase the possibilities of vertex migration. Several experiments over a set of real data were used. The results showed a new and efficient way to solve this problem, in which the algorithms improved both the solution´s quality and the formation of valid solutions.