【摘 要】
：
本文考虑一种限制性路增广问题,其具体描述为:给定一个赋权有向图D=(V,A;w;s,t),其中w:A → R+,s,t∈V,及子图D0=(V0,A0),要求寻找弧子集A1∈AA0,满足诱导子图D[A0∪A1A2]
论文部分内容阅读
本文考虑一种限制性路增广问题,其具体描述为:给定一个赋权有向图D=(V,A;w;s,t),其中w:A → R+,s,t∈V,及子图D0=(V0,A0),要求寻找弧子集A1∈A\A0,满足诱导子图D[A0∪A1\A2]中存在从s到t的有向路,目标是使权重w(A1)=∑e∈A1w(e)达到最小,这里A2是由A0中任意k条弧构成的集合。本文首先证明了限制性路增广问题是Max-SNP困难的,设计了一个(k + 1)-近似算法求解该问题,其复杂度为O((k + 2)nm);对于子图D0中存在k条弧不交的s-t有向路的限制性路增广问题,设计了一个多项式时间最优算法求解该问题,时间复杂度为 O((k + 1)nm)。
其他文献
国电建投内蒙古能源公司布连电厂发电党支部严格按照集团公司提出的重视基层班组建设,打通企业管理"最后一公里"相关精神要求,创新性提出"党建+班建,党建促班建"的"双组同行,
Theil-Sen估计是Theil[3]在1950年提出,Sen[17]在1968年将其推广。这个方法的基本估计思想是在一元线性回归模型中,首先任取两对观测值求解斜率,再对斜率取中位数作为斜率参
背景:多发性骨髓瘤(MM),是血液系统最常见的恶性肿瘤之一[1]。异常的浆细胞浸润骨髓及髓外组织,并合成单克隆免疫球蛋白及其轻链,可引起骨骼疼痛、骨骼破坏、贫血、肾功能不全及免疫功能异常等[2]。在生活方式、环境等多种因素的影响下,多发性骨髓瘤的发病率呈上升趋势,严重威胁着患者的身心健康。导师李仝教授从事中西医肿瘤血液方面工作30余年,临床经验丰富,尤其在治疗多发性骨髓瘤方面,具有一定的临床治疗特
褐藻胶是从海带等褐藻细胞壁中提取的一种水溶性酸性大分子,由β-D-甘露糖醛酸（β-D-mannuronate,M）及其C5差向异构体α-L-古罗糖醛酸（α-L-guluronate,G）交替组成其线性多糖结构
本文是一篇访谈类英汉模拟交替传译实践报告,主要研究的是当两种语言之间存在较大差异,不能按源语形式表达思想时,运用增补法和省略法这两个翻译技巧重新组织行文。省略能使语言简练、紧凑、明确,有利于突出新信息,夸克等人称其为“语法省约”。省略不是随随便便的省略,也不是省略掉原文的内容和信息,而是在忠实原文的基础上更好地表达原文信息的一种表达手段。增补则是在原文的基础上,增加必要的词语、分句乃至整个句子,使
齿轮箱是高速列车动力传递系统的重要部件之一,其服役的可靠性、安全性以及稳定性将直接影响到高速列车的正常运行。在高速列车运行的过程中,齿轮箱需要承受电机扭矩变化带来的冲击以及轮轨激励下的振动等复杂载荷,其服役环境非常恶劣,在使用过程中极易产生疲劳破坏。因此,研究齿轮箱的疲劳裂纹萌生和扩展规律具有重要的理论意义和应用价值。分析了国内某型380公里级高速列车齿轮箱体在使用过程中的受力情况及疲劳裂纹的萌生
薄皮甜瓜(Cucumis melo var.makuwa Makino)的经济价值较高,给甜瓜栽培带来了巨大的潜力,但是作为呼吸跃变型果实,加上本身香甜多汁的特性,在采后极易腐烂。嫁接作为一种可以克服连作障碍,增强植株长势,改善植株抗逆性的方法被广泛应用。在生产中,嫁接出现推迟果实成熟期,降低果实的品质的现象,对货架期果实品质特性也产生一定影响,进而影响果实的后熟过程,为研究嫁接对薄皮甜瓜货架期果
随着城市发展水平的提高和对畅行环保的公共交通需求,我国地铁建设进入快速发展阶段,盾构施工在地铁建设中应用逐渐普及。地铁盾构施工产生的土体变形和地表沉降会影响施工安全,尤其在下穿结构物时成为重要的风险源。目前国内外对地铁盾构施工引起的沉降分析主要基于直线线形,线路转向导致的小半径曲线条件下沉降计算模式的适用性问题需要进一步研究。论文通过理论分析、数值模拟研究了小半径曲线条件下地铁盾构施工引起的地表沉
目的:本课题从经络角度,观察寻常型银屑病的主要皮损分布部位,分析皮损在十二皮部的分布规律,归纳出寻常型银屑病患者常见的经络证型,并总结出各经络证型的主要症候。方法:以问卷形式收集原始资料,并将皮损以图片及绘图方式记录,采集符合纳入标准的213例寻常型银屑病患者的一般情况、皮损分布及所在皮部、中医四诊等信息,记录于“银屑病患者就诊信息采集表”,总结不同部位皮损在十二皮部出现的频数及所占百分数,归纳出
本文主要研究限制顶点度的最小K-树问题,该问题是限制顶点度的最小支撑树和最小K-树问题的推广。限制顶点度的最小K-树问题具体描述如下:给定一个图G=(V,E;ω,K),|V|=n +1,ω