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.
Submitted to: Neurocomputing.
Download Info
To our knowledge, this item is not available for
download. To find whether it is available, there are three
options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page
whether it is in fact available.
3. Perform a search for a similarly titled item that would be
available.
Publisher Info
Paper provided by Santa Fe Institute in its series Working Papers with number
98-07-062.