【摘 要】
：
该文分两章.第一章研究了带时间和边数约束的双约束最短路问题.这类问题是NP-完备的,不存在多项式时间精确算法,除非P=NP.作为预备知识,我们首先介绍了ROUNDING和SCALING方法
论文部分内容阅读
该文分两章.第一章研究了带时间和边数约束的双约束最短路问题.这类问题是NP-完备的,不存在多项式时间精确算法,除非P=NP.作为预备知识,我们首先介绍了ROUNDING和SCALING方法的原理以及如何运用它全多项式时间近似方案(FPAS).第二章研究了带边数约束的点点连接问题.通过观察我们看到这个问题的最优解具有特定的结构,即它不可能有两个或两个以上的共同部分以前向的顺序依决出现;一个由两条路P<,1*>和P<,2*>构成的最优解,其公共部分必然是以反向的顺序被两条路共享.最后,分析整个算法的时间复杂性知道,它是一个多项式时间算法,可以在O(n<7>)时间内求解原问题.
其他文献
该文主要讨论了一类具有星形结点的平面四次多项式微分系统的全局结构及其条件、例子,并给出其相应的全局结构相图.文章借鉴了叶彦谦教授、李学敏教授等对具有星形结点的平面
在带有红树林的近海渔业资源中，本文假设鱼群的繁殖行为仅仅在红树林区进行，并且在该区域严禁捕捞，在此基础上建立了一个近海渔业资源的离散动力学模型，并分析其非线性动力学行为
设λK是有v个顶点的完全多重图,G=(V(G),E(G))是有限简单图.一个(v,G,λ)-GD是将λK的所有边分拆为与G同构的子图(称为区组)的并.称(v,G,λ)-GD为对于图G的图设计或G-分解.(v
该文讨论某些李群以及某些与李群密切相关的流形的几何性质.该文大致可分为两部分.第一部分,主要讨论幂零及可解李群的几何.第一部分的安排如下.在第一章中,我们重提广义Heis
在二维非结构化网格自动生成的研究中,四边形网格和三角形网格是当前应用最为广泛的两类网格.目前,三角形网格的自动生成技术己趋成熟,但关于任意四边形网格自动生成技术还不
证券投资组合绩效评价是从事后对证券投资组合的效果进行比较客观公正的评价.一般的评价指标为投资组合的收益率及风险.已有的评价方法主要是根据资本市场线和证券市场线,给
Rayleigh-Taylor不稳定性问题是由于两种不同密度的流体在重力或惯性力作用下形成的界面不稳定问题.该文重点用数值模拟的方法研究三维Rayleigh-Taylor不稳定性问题.求解不稳
拓扑传递性是动力系统的一个全局性质,它描述了动力系统有一个状态可以在该系统的作用下进入任意状态的任意邻域中.该文针对Takens-Rullue意义下的混饨(简称TR-混饨)的拓扑传
近几年来,随着非线性科学的快速发展,非线性方程已经成为非线性学科里重要的研究部分.非线性方程是描述各个科学领域中复杂的物理现象的一类重要的数学模型,求解偏微分方程是
在Internet和其他的很多信息量高度集中的媒体上,信息检索(Information Retrieval,IR)正日益成为一个重要的课题.在潜在语义分析(Latent Semantic Analysis,LSA)方法中,相关