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.