基于分子信标的图的最小顶点覆盖问题

摘要

生物芯片技术和DNA计算分别是近几年来生命科学与信息科学的新兴研究领域，DNA计算在求解NP问题上存在着硅计算无法比拟的先天优越性。而图的最小顶点覆盖问题是图论中的一个重要问题，目前还没有好的算法。在DNA计算和DNA计算芯片的基础上，采用分子信标编码策略，利用观察荧光来确定图的最小顶点覆盖问题的可行解。利用分子信标模型来解决图的最小顶点覆盖M题，和其它DNA计算方法相比，该方法操作起来更加方便。