Self-organizing maps with variable local topology are shown to constitute a reasonably good heuristic to find approximate solutions to the NP-complete k-way graph partitioning problem, where a weighted graph has to be divided into k clusters of equal size while minimizing the total weight of inter-cluster edges. The equal size constraint is implemented through a distribution of training points that the map tends to approximate, and the minimal cut constraint is implemented through the simultaneous update of neighboring nodes. A mean-field analysis suggests that the complexity of the algorithm is at most in , where n is the number of vertices of the graph, and the number of edges. This prediction is tested on a class of random graphs. <p> <p> <p> Submitted to: Neurocomputing.
