GRAPH PARTITIONING USING LEARNING AUTOMATA

Given a graph G, we intend to partition its nodes into two sets of equ al size so as to minimize the sum of the cost of the edges having end- points in different sets. This problem, called the uniform graph parti tioning problem, is known to be NP-Complete. in this paper we propose the first reported learning-automaton based solution to the problem. W e compare this new Solution to various reported schemes such as the Ke rnighan-Lin's algorithm, and two excellent recent heuristic methods pr oposed by Holland et al.-an extended local search algorithm and a gene tic algorithm. The current automaton-based algorithm outperforms all t he other schemes. We believe that it is the fastest algorithm reported to date. Additionally, our solution can also be adapted for the GPP ( See note at end of Section 1) in which the edge costs are not constant but random variables whose distributions are unknown.