最大匹配问题的分子信标计算模型

摘要

目前利用DNA计算求解图与组合优化中探索和开发新的分子结构是研究的一个热点,而分子信标具有结构简单、灵敏度高、易于检测及反应迅速等优点。最大匹配问题是一个著名的NP-完全问题,文章利用分子信标给出最大匹配问题的DNA计算模型。该模型具有编码简单、耗材低、空间利用率高、操作时间短及易于检测等特点,同时拓展了DNA计算解决问题的方法和应用领域。