【摘 要】
：
割集问题(cut problem)在图论和组合优化中占有重要地位,如经典的最大流最小割集定理。同时它对有些问题的算法设计有很大帮助,在现实中应用非常广泛。割集问题有很多较为复
论文部分内容阅读
割集问题(cut problem)在图论和组合优化中占有重要地位,如经典的最大流最小割集定理。同时它对有些问题的算法设计有很大帮助,在现实中应用非常广泛。割集问题有很多较为复杂的推广问题,如多割问题(multicut problem)和多向割问题(multiway cut problem)等。不同领域的研究者对它的这些推广问题做了研究并得出了一些相应的成果。本论文主要讨论的是割集推广问题中的限制在两类特殊图环和树上的点多割问题。对于限制在树上的点多割问题,我们首先说明该问题是NP-完备的；其次本文借助线性规划理论中的互补松弛条件设计了一个时间复杂度为O(max｛k·n,nlog n｝)且近似值为2的算法。对于环上的限制性的点多割问题我们说明了它在多项式时间内可解。
其他文献
本文研究了某些高阶齐次线性微分方程解的零点收敛指数.
第一部分,概述了本研究领域的研究近况.
第二部分,研究了一类高阶齐次线性微分方程
f(k)+Ak-2f(k-2)+
本文主要应用Nevanlinna值分布理论和Wiman-Valiron理论对复域差分,差分方程的亚纯解,以及Riccati微分方程的亚纯解进行了研究.全文共四章.
第一章,介绍了基本概念和记
《中国共产党党内监督条例(试行)》(以下简称《党内监督条例》)的颁布实施,是贯彻落实“三个代表”重要思想和十六大精神、加强和改进党的建设特别是制度建设的一个重大举措,
今年上半年我省消费品零售总额增速加快,但总体运行还是表现为需求不足,消费不热,市场物价继续走低,通货紧缩没有明显的改观,上半年我省居民消费价格总水平下降0.5%,其中:城
入侵检测技术是一种重要的动态安全防护技术,现已成为信息安全中的一个重要研究方向,可分为异常检测和误用检测,本文将主要研究异常检测。异常检测首先要构建正常行为的模型,
本文目的是研究U-富足半群中的弱U-纯正半群的结构.以包含在(H)U中的最大同余μ,最小Ehresmann半群同余δ为工具,证明了弱U-纯正半群与基本拟-Ehresmann半群((S,U)/μ,U/μ)
本文主要研究的是两类种特殊的子流形的形变。一类是紧致带边的特殊勒让德(special Legendrian)子流形；另一类是渐进的特殊拉格朗日子轨形(asymptoticallyconical special Lag
本文采用贝叶斯网络图模型的方法探讨了国内期货白糖价格,国内现货白糖价格和国外期货白糖价格三者间的因果关系。
一方面,我们采用模型选择的方法以及五种不同的得分机
设G为有限群.令πe(G)={n∈N｜G有元素g,使｜g｜=n}.即πe(G)为G的元素阶的集合.令N(G)={n∈N｜G有共轭类C,使｜C｜=n}.即N(G)为G的共轭类长的集合.
1987年,苏州大学施武杰教授提出
本论文研究了在时间尺度上的微分方程组的多个正周期解的存在性以及具有脉冲和自由时滞的广义神经网络的反周期解问题，并得到了一系列新的结果。
在第一章中，我们介绍本文