【摘要】NP难解问题是理论计算机科学的主要研究对象,对NP难解问题提出实际有效的固定参数可解算法是理论计算机科学中的一个新的研究方向。参数计算方法是求解实际应用问题的一种新的有效手段,目前己在相当多领域中得到了成功的应用。本文选取社会学和生物信息学中的正负支配、三值支配、联盟和序列结构比对等经典的NP难解问题为研究对象,对这些问题进行参数化建模后,基于树分解技术并综合运用核心化、分支限界、动态规划 […]