Abstract
Replica-symmetric solutions of the graph-bipartitioning problem with finite connectivity are presented. With the constraint =0 strictly enforced, another solution can be obtained, which gives a lower cost function than that given by the spin-glass solution. It is believed that this new solution is currently the best candidate for the true solution of the graph-bipartitioning problem.
- Received 11 May 1987
DOI:https://doi.org/10.1103/PhysRevLett.59.1625
©1987 American Physical Society