Solving the minimum bisection problem using a biologically inspired computational model

The traditional trend of DNA computing aims at solving computationally intractable problems. The minimum bisection problem (MBP) is a well-known NP-hard problem, which is intended to partition the vertices of a given graph into two equal halves so as to minimize the number of those edges with exactly one end in each half. Based on a biologically inspired computational model, this paper describes a novel algorithm for the minimum bisection problem, which requires a time cost and a DNA strand length that are linearly proportional to the instance size.

Authors

• Xingchang Liu
• Xiaofan Yang
• Shenglin Li
• Yong Ding

Keywords

• DNA algorithm
• Adleman–Lipton-sticker model
• Minimum bisection problem