论文部分内容阅读
本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。
一类NP—完全问题在阈图上的解
【摘 要】
：
本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。
【机 构】
：
山东大学,山东大学
【出 处】
：
计算机学报
【发表日期】
：
1989年1期
【基金项目】
：
自然科学基金
其他文献
<正> 1.引言 以往对数据库的修改:增、删、改都是针对数据库模式中的数据进行的,数据库模式则在运行中保持不变。我们不再对其属性和依赖集进行修改。知识库、专家数据库等均
本文提出一个简洁的、完整的、统一于非自交多边形(NIP)的多边形三角剖分算法,该算法分成两部分:其一是将任意多边形转化为非自交多边形;其二是非自交多边形的三角剖分。最后给出该算法在三维立体造型中的应用。
本文提出了一种状态空间搜索方法RA,此方法能寻找出具有最大耗散值的目标结点(在有限空间);借助RA给出了最佳初始分配算法,并讨论了具有负符平衡要求及其它附属条件的最佳初