Abstract:
Domatic partition problem is one of the classical NP complete problems, which is widely used in various areas.However, it has no polynomial time solution so far.DNA computing is a method which has very strong parallel computing power, and the sticker model which is based on the sticker operator is one of the computing models in DNA computing area.In this paper, it puts forward an algorithm based on the sticker model, which can solve the domatic partition problem, and the algorithm can find the feasible solutions through two steps in polynomial time.To prove the feasibility of the algorithm, it uses a java program to simulate the algorithm, and the results of the program running on the computer prove the correctness and the effectiveness of the algorithm.