【摘 要】
：
顶点覆盖问题是经典的组合最优化问题.顶点带非负权重的顶点覆盖问题在一般图上是NP-难的,而在二部图上却能在多项式时间之内被解决.解决二部图上的顶点覆盖问题,可利用二部图的特殊结构,通过考虑一个叫所谓边装填的问题得到解决.边装填问题可认为是匹配问题的推广,并在二部图上,恰好成了顶点覆盖问题的对偶问题.本文形式化描述边装填问题并主要研究和分析解决边装填问题的算法时间复杂度.给定一个顶点有非负整数权重的
论文部分内容阅读
顶点覆盖问题是经典的组合最优化问题.顶点带非负权重的顶点覆盖问题在一般图上是NP-难的,而在二部图上却能在多项式时间之内被解决.解决二部图上的顶点覆盖问题,可利用二部图的特殊结构,通过考虑一个叫所谓边装填的问题得到解决.边装填问题可认为是匹配问题的推广,并在二部图上,恰好成了顶点覆盖问题的对偶问题.本文形式化描述边装填问题并主要研究和分析解决边装填问题的算法时间复杂度.给定一个顶点有非负整数权重的图G=（V;E;w）,如果G中一个边的集合F（边允许重复）,对G中任意一个顶点v,满足v在F中出现的次数不超过w（v）,则称F是图G的一个边装填.一个边装填的权重就是这个边集中所有边（出现的次数按重数算）的权重之和.最大边装填问题就是在给定的赋权图中找出权重最大的一个边装填.本文对边装填问题的研究有:描述了点赋权一般图上最大边装填问题的多项式时间可解性,给出了 O（（|E|+|V|log|V|）（|V|2log|V|））的多项式时间算法.对点赋权为2的一般图,给出了关于此问题时间复杂度为（?）的多项式时间算法.将点赋权二部图上最大边装填问题的算法时间复杂度改进到（?）.同时,对于一般图上顶点覆盖问题的一个近似因子为2的近似算法,利用极大边装填的组合性质给出了一个新的证明.
其他文献
在中国老龄化的大势下,老年人已经成为城市公园绿地的主要使用者,城市公园对于丰富老年人日常生活能起到重要的促进作用。本文以昆明城市公园中老年人活动频率高的空间为研究对象,尝试提出基于微气候适应性设计机理的老龄化公园景观设计策略。本研究首先通过对老年人群活动行为进行实地调研获得老年人活动喜好及规律,据此总结提炼出与老年人活动行为相关的景观要素。并对上述总结选取的公园活动空间进行微气候实测,基于实测结果
1905年昆明自开商埠,1910年滇越铁路建成通车,加快了昆明近代化工业的发展进程,经过漫长的孕育时间留下了许多风格独特、价值珍贵的工业建筑遗产。在当前城市化进程及工业转型提升的大背景下,许多工业遗产被忽视或正遭到不同程度破坏、损毁,其重要的原因即在于工业建筑遗产的价值得不到真正的认知,没有针对性的评估方法。只有基于对昆明近代工业建筑遗产各方面的价值充分把握的基础上,建立准确、适用的昆明近现代工业
环糊精因其具有分子识别、易衍生化、经济环保和生物安全等特性已经被广泛应用于药物载体和超分子催化等领域。在药物载体领域,环糊精作为天然低聚糖分子,具有较好的水溶性,其羟基易衍生与难溶性药物共价结合形成药物-环糊精偶合物进而提高药物的水溶性、稳定性以及生物利用度。在超分子催化领域,环糊精以类似于天然酶的形式用于水相催化。其空腔能够包合疏水性底物,形成特定的主-客体包合物,固定底物的空间位置并利用羟基或
呼吸道感染（Respiratory tract infections,RTI）是医院最常见的高度传染性疾病,还常伴有流感及流感样疾病的发生。逐年上升的发病率和死亡率使呼吸道感染成为了全球性问题。呼吸道最初被认为是无菌的,但是随着研究的发现,呼吸道中存在大量定植的共生微生物,且对人体健康有很大影响。人类处于正常生理状态时,呼吸道中的共生菌相互制约使其维持在某个相对平衡的状态。对于新生儿,这种稳态受生
食源性活性肽由于来源广泛、无毒副作用和成本低廉而成为慢性疾病防治领域的研究热点。有研究证明酸驼乳具有调节血压、降血糖等多种生活性。近年来,有关鲜驼乳和发酵驼乳在辅助治疗糖尿病和高血压方面的研究逐渐增多,但是研究发酵乳的生物活性与发酵菌种之间关系的报道却较少。本研究利用来自传统发酵乳的乳酸菌和酵母菌发酵驼乳,筛选出高产血管紧张素转化酶（ACE）和二肽基肽酶Ⅳ（DPP-Ⅳ）抑制肽的菌株,分离、鉴定和合
傣族竹构建筑凝结着傣族人民的聪明智慧,是他们顺应自然、在长期的生活实践中不断总结的成果。然而在现代化的今天,傣族村寨竹构建筑因防霉、防腐、防蛀以及节点连接方式上的一些问题,其建筑耐久性和审美需求不能够适应当下时代的发展。当前,傣族竹构建筑的发展迎来了一个新的契机,随着近年来大家对生态、绿色、可持续建筑的关注度提高,大家的目光又重新回到了竹子这一传统材料上,竹构建筑逐渐成为建筑界研究的热点,同时有许
近年来,世界各国面临着能源和环境的共同压力,各行各业都开始探索绿色节能的发展道路。有研究表明,我国建筑行业的能耗占社会总能耗的30%左右,十三五规划将建筑节能上升到国家高度。北方农村住宅由于量大面广,受地区经济文化等因素的影响较大,建筑节能工程推进较为缓慢,因能耗高、节能潜力巨大而成为全面实现建筑节能的突出短板。论文以河南省济源市农村住宅为研究对象,经过对当地农村住宅的深入调研,采用主观调查问卷、
干旱胁迫导致土壤中水分减少,对作物的生长发育和存活造成严重影响,已成为了制约农业生产的重要环境因素之一。植物响应干旱胁迫的信号通路主要有ABA依赖的信号通路和非ABA依赖的信号通路,ABA依赖的信号通路中ABA作为第二信使调控下游靶基因的表达已经众所周知。而非ABA依赖的信号通路知之甚少,干旱胁迫条件下植物根的形态结构与植物激素之间的相互作用提高植物耐旱性的作用机理研究较少。本论文主要对mi R3
癌症是全球重要的公共卫生问题,2020年全球癌症统计分析报告指出,肺癌是全球导致死亡人数最多的癌症。肺癌在临床上的治疗方法主要包括手术治疗、化学治疗、放射治疗、靶向治疗和免疫治疗。近年来,中医药在肺癌患者的治疗中体现了独具特色的疗效,尤其是中药与化疗的联合使用,可增强化疗的敏感性,缓解耐药性,降低不良反应发生率,改善患者生活质量。因此,为了提高肺癌的诊疗效果,探索中医药与常规西医疗法的协同作用,具
全取代的1,2,3-三氮唑是一类非常重要的含氮杂环化合物,在对原有药物的改良或新型药物的研究开发、与生物分子之间的缀合以及先导化合物库的建立等诸多领域发挥着越来越重要的作用。鉴于铜催化末端炔烃和有机叠氮化合物的1,3-偶极环加成反应（Cu AAC）具有产率高、区域选择性好、反应速率快且具有普适性和可靠性等优点,因此在Cu AAC反应的基础上发展出的多组分串联环加成反应已经成为了构建全取代1,2,3