【摘 要】
：
边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了最坏情况界为2的多项式时间近似算法,并给出近似算法的紧例及其分析。
【机 构】
：
杭州电子科技大学理学院,台州学院电子与信息工程学院
【基金项目】
：
国家自然科学基金资助项目(11971139,11771114)。
论文部分内容阅读
边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了最坏情况界为2的多项式时间近似算法,并给出近似算法的紧例及其分析。
其他文献
以GB 20176—2016《民用建筑热工设计规范》为理论依据,以严寒地区典型城市气候条件为分析基础,选取模塑聚苯乙烯泡沫塑料保温板(简称EPS保温板)、挤塑聚苯乙烯泡沫塑料保温板(简称XPS保温板)、聚氨酯硬泡沫塑料保温板(简称PUR保温板)作为夹心保温层材料,研究预制混凝土夹心保温外墙板的内部的冷凝情况。分析计算满足标准规定的质量湿度允许增量要求的保温材料最小厚度δi·min,结果表明,在同样相对湿度计算条件下,XPS材料δi·min最低,EPS次之,PUR最高;同类保温材料在冬季室外温度更低而采暖期
基于硅基65 nm互补金属氧化物半导体(Complementary Metal Oxide Semiconductor,CMOS)工艺,设计了一款工作频率为91.6~93.2 GHz的压控振荡器(Voltage Control Oscillator,VCO)。使用基于变压器结构的高品质因子电感改善了VCO电路的相位噪声,并采用金属氧化物半导体场效应晶体管(Metal-Oxide-Semiconductor Field-Effect Transistor,MOSFET)开关阵列和变容管共同实现了该VCO电路
选择浙江省宁波市某交通主干道和安吉县某生态示范村为研究对象,对其周边土壤的多环芳烃(Polycyclic Aromatic Hydrocarbons,PAHs)含量、组成、来源、分布和风险进行对比研究。研究结果发现,交通主干道周边土壤PAHs含量范围在117.9~18784.3 ng·g-1,平均值为2800.8 ng·g-1;生态示范村周边土壤PAHs含量范围在22.0~614.7 ng·g-1,平均值为120.2 ng·g-1
通过快冻法开展透水再生混凝土冻融试验,对不同再生粗骨料取代率下的动弹性模量、抗折强度以及立方体抗压强度进行测试,验证冻融循环作用对透水再生混凝土力学性能的影响。试验的结果表明,随着冻融循环次数或者再生粗骨料取代率的增长,透水再生混凝土的相对弹性模量、相对抗折强度以及相对立方体抗压强度三者都会随之下降,衰减速率由大到小依次为相对抗折强度、相对立方体抗压强度以及相对动弹性模量。将损伤变量定位为动弹性模量,利用数据拟合可知,运用函数来表现透水再生混凝土的相对抗折强度、相对立方体抗压强度以及损伤度,其相关性均较好
在全球少子老龄化趋势下,发达国家首先出现了“老幼复合”的实践探索并取得积极效果,然而由于地域环境的转换和社会背景的差异,国外经验在中国应用具有不确定性。研究调查和归纳我国老幼复合的业态类型与建筑组合方式,针对唯一可持续发展的综合社会福利设施的老幼复合,探讨社会资源紧缺对其的刺激作用,揭示“社会资源利用效率”是综合社会福利设施老幼复合发展的核心动力;进而挖掘老幼复合综合社会福利设施在政策与法规、社会与需求、以及设施与空间层面的问题与缺失,由此阐释“老幼复合”综合社会福利设施相关研究发展动态与趋势
为了解决脑机接口中识别率低、稳定性差等问题,提出一种基于张量网络的多脑脑机接口解码方法。首先,用共空间模式提取脑电特征,融合多脑信息,将融合的数据输入张量网络以便捕获时序特征;然后,张量网络把参数表示成高维数组,运用张量分解方法分解神经网络的权重张量,在不影响识别准确率的前提下,削减了神经网络的参数数量。实验结果表明,与单个被试相比,多脑运动想象脑电数据的识别准确率提高了17.2%;与GRU网络相比,张量网络模型的识别准确率有所提高,同时网络中的参数数量更少。
随着知识经济的崛起,创新成为城市的重要职能之一,并且产生了新的空间需求。从创新空间网络的视角出发,对创新网络与空间结构的相关性进行研究,有助于营造适应创新活动需求的城市空间环境,促进创新活动与空间营造良性互动。创新空间网络的绩效评价包括邻近性、集聚性、中介性、持续性等四个维度以及个体和群体两个层面。运用UCINET和UNA建立创新网络模型和空间网络模型,进而基于ArcGIS实现两类模型的数据转换,可对创新空间网络绩效进行量化可视评价。
为了使硫铝酸盐水泥满足3DP法模型打印的要求,研究了硅粉掺量对复合粉体密度参数及铺粉性能的影响;测试了不同PVA掺量下的打印液渗透参数;测试了不同打印头饱和度下的打印精度及强度;测试了试样经饱和氢氧化钙溶液浸泡3、7 d的单轴抗压强度,并利用XRD和SEM分析了打印试样的水化产物和微观形貌。研究表明:硫铝酸盐水泥基材料能够打印具有较好成型精度的复杂模型,并且模型具备一定的成型强度。Z向的早期抗压强度为0.88 MPa,经饱和氢氧化钙溶液浸泡养护3 d的抗压强度为5.09 MPa,养护7 d的抗压强度为7.
研究一类非齐次Markovian跳变随机奇异区间二型模糊系统的随机容许及镇定问题。运用有限分段齐次思想来处理时变的转移速率。首先,构造随机Lyapunov函数,采用广义Ito公式及不等式放缩技术,得到系统随机容许的充分条件;其次,在状态反馈模糊控制器的设计过程中,引入由特定矩阵变量构成的线性变换,将非线性矩阵不等式转化为线性矩阵不等式。此方法的实用性最终通过数值仿真得以验证。
针对频谱感知算法检测概率较低的问题,提出一种基于随机矩阵和能量双联合的协作频谱感知算法。根据随机矩阵理论,对最大最小特征值(Maximum Minimum Eigenvalue,MME)算法进行优化,并联合能量检测算法进行协作感知。在已知虚警概率情况下,对门限值进行推导。仿真结果表明,提出的算法与特征值之比改进算法、传统MME算法、能量检测算法相比,低虚警概率情况下的检测概率大约提升了43%,低采样点数情况的检测概率大约提升了2%。在保持较高检测概率的同时,信噪比大于-11 dB情况下,相比特征值之比改进