【摘 要】
：
骨架分析是近年来理论计算机科学研究的热点,对于NP-难解问题的启发式算法设计具有重要意义.由于骨架计算复杂性研究十分困难,现有的骨架分析方法多采用实验统计手段.针对现
【机 构】
：
大连理工大学软件学院,中国科学技术大学计算机科学与技术系
论文部分内容阅读
骨架分析是近年来理论计算机科学研究的热点,对于NP-难解问题的启发式算法设计具有重要意义.由于骨架计算复杂性研究十分困难,现有的骨架分析方法多采用实验统计手段.针对现有方法中存在的骨架规模小的缺陷,给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法,有效提高了骨架的规模.同时,利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题,即在的假设下,不存在多项式时间的算法可以确保得到GBP问题的完整骨架.本文的工作拓广了骨架计算复杂性研究的范围,所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.
其他文献
利用复变函数方法,通过构造保角映射,研究了一维六方准晶中具有不对称裂纹的圆形孔口的反平面剪切问题,给出了Ⅲ型裂纹问题的应力强度因子的解析解,在极限情形下,不仅可以还
讨论矩阵方程ATXA=D,该方程源于振动反问题和结构模型修正.本文利用Moore-Penrose 广义逆的性质,给出该方程解的条件数的上、下界估计.同时,利用Schauder不动点理论给出该方
降晰参数识别在模糊图像恢复过程中具有很重要的作用。在各种图像捕获系统中,有两种形式的图像模糊比较常见:一种是由光学系统散焦造成的散焦模糊;另一种是物体与照相机之间的相对运动造成的运动模糊。相对单个模糊模型的参数识别来说,混合了散焦和运动模糊的图像,其模糊参数的识别要复杂得多。许多识别方法一般都是用来分析某一特定的模糊模型的,而对两种模糊混合在一起的情况来说是很难区分的。提出了一种倒谱分析方法,在倒
讨论了Clifford分析中双曲调和函数的一个带位移的非线性边值问题,先讨论了解析函数的一个边值问题的解的存在性,然后利用Clifford分析中双曲调和函数与解析函数的关系讨论了
应用分析方法,研究了一类二阶非线性差分方程解的振动性质,获得了一个新的振动性定理,推广和改进了已知的一些结果.
采用递推算法计算任意数目三维层状单轴各向异性介质的并矢Green函数.根据层界面处电场和磁场的连续性条件得到3个确定Sommerfeld积分待定系数的线性方程组,分别对应于垂向单
随机模糊立体运输问题的研究是为了解决现实生活中双因素不确定性问题,在遗传算法的基础上,运用可信性理论建立随机模糊运输问题的机会约束规划模型.通过算例进行VC++编程模
以β-氯乙基苯醚、苄氯、N-甲基咪唑、浓硫酸等为原料,通过多步反应合成了在N-甲基咪唑阳离子上分别含烷氧基苯磺酸和烷基苯磺酸侧链结构的两种水溶性、室温下呈液相的新型Br
提出了Bézier样条曲线利用分割技术近似弧长参数化的一种方法,并给出了相应的算法.通过求出曲线上所谓的最坏点并在相应点处进行分割,可得到两条Bézier样条曲线.让这两条B
通过卷积法和最小二乘法,处理Ga-Mo／HZSM-5催化剂上形成碳的XAES数据。同时,建立了光滑XAES数据点的数学模型。由碳的KVV俄歇光谱数据一阶(dN／dE)和二阶(d2N／dE2)导数结果表明,