Abstract: There is an issue of A/B plane partition of HSTPs in the topology optimization of CCS7 network. It can be formulated into a new kind of graph partition problem. The problem is proved to be NP-complete, so the neural network, the genetic algorithm and the simulated annealing are applied to solve it. In order to make the algorithms comparable, the testing schemes are carefully designed. The computing results for the three algorithms show that the genetic algorithm and the simulated annealing are quite robust for the problem, they can search out the optimum with a larger probability and a higher efficiency.

Key words: signaling networks, A／B plane partition, NP-completeness, heuristic algorithms