2. 您的位置
3. 首页
4. 期刊论文
5. 次模函数近似算法求最小颜色生成树

次模函数近似算法求最小颜色生成树

来源 :新疆大学学报：自然科学版 | 被引量 : 0次 | 上传用户：camino

【摘 要】

：

给定图G并对其进行边着色,G的最小颜色生成树（MCST）问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有

【作 者】

：

李学良 涂建华 

【机 构】

：

南开大学组合数学中心

【出 处】

：

新疆大学学报：自然科学版

【发表日期】

：

2008年4期

【关键词】

：

边着色图 最小颜色生成树(MCST) 最大颜色匹配(MCM) 次模函数 近似算法 Edge-colored graph minimum color spann 

【基金项目】

：

Supported by NSFC, PCSIRT and the ＂973＂ programm.

下载到本地 , 更方便阅读

下载此文 赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

给定图G并对其进行边着色,G的最小颜色生成树（MCST）问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论（贪婪算法的思想）给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.

其他文献

开发性金融贡献度系统的分析设计

开发性金融对支持我国各地区的基础设施建设、高新技术企业发展等起到了重要的作用，客观、定量地分析开发性金融贡献度，对促进开发性金融发展有重要意义。本文从系统分析、系统

期刊

开发性金融贡献度系统分析系统设计

一类正则图的边坚韧度

证明了一类r-正则r=k＇（G）连通非完全图G的边坚韧度近似等于r/2（1＋1/│V（G）-1│）并且提供了估计一些特殊图类的笛卡儿积和Kronecker积的边坚韧度的公式．

期刊

边坚韧度笛卡儿积KRONECKER积Edge-toughness Cartesian product Kronecker product

熔融法在粗杂铜取制样方法中的应用

介绍了将熔融法用于品质不均匀的粗杂铜的制样方法.试验表明铜、金、银品位波动较大的粗杂铜样本通过熔融的方法可以制成品质均匀的试样,熔融制样前、后铜金属量平均回收率大

期刊

熔融法品质粗杂铜制样方法铜金属量Melting method Quality Blisters and scraps Sample preparat

丁建丽教授简介

丁建丽，男，汉族，1974年4月出生，中共党员，教授，博士，博士生导师，现任新疆大学研究生院副院长。

期刊

博士生导师研究生院新疆大学副院长

一种基于OGC Web服务的WebGIS的解决方案

在介绍了W ebGIS的特点、系统结构以及目前存在的不足之后,对开放地理信息系统协会(OpenGIS Consortium,OGC)的地理信息W eb服务规范做了比较详细的论述,并基于OGC W eb服务(OGC W eb Service,OWS)提出了一种新的W ebGIS框架。以渔业W ebGIS系统为例给出一个解决方案,探讨了其关键技术和创新之处,指出了进一步的工作和研究方向。

期刊

WEB服务OWSWEBGIS地理信息Web服务MAPXTREME工作流

钩吻配伍玉叶金花对大鼠脏器组织病理形态改变及扭体镇痛实验研究

目的研究钩吻与玉叶金花配伍后能否降低毒性保持镇痛药效。方法将SD大鼠分为空白对照组、钩吻组(0.36 g·kg-1)、钩吻与玉叶金花配伍组(0.36 g·kg-1+14.4 g·kg

期刊

钩吻玉叶金花HE染色病理形态镇痛Gelsemium elegansMussaenda pubescensHE stainingPathological

跳远技术分析与训练

优秀的跳远运动员,也常是杰出的短跑选手。因此,他的训练应以高质量的短跑训练为基础,加之以合理的秋季耐力训练。抓速度的同时,还必须有力量,以便把水平冲力转变为垂直升力,

期刊

跳远技术短跑训练跳跃项目踏跳神经肌肉系统耐力训练训练方法身体重心加速跑速度优势

创建江铜资金结算中心的管理新模式探讨

随着江西铜业集团公司生产经营规模的不断扩大,经济总量和内部关联交易结算量大幅提升,由于过去未实行集中统一的资金结算与管理,集团资金管理曾出现三个比较突出的问题,即:

期刊

资金结算中心集团资金集中管理Cash settlement Group company's capital Centralized managem

纯氮气反应溅射c-轴择优取向AIN薄膜的制备及性质研究

在纯氮气气氛、衬底温度为20℃至370℃的条件下，分别在硅（100）和石英衬底上沉积氮化铝薄膜．原子力显微镜图片表明：在不同衬底温度制备的薄膜表面平滑，均方根粗糙度为2．2—13．2nm．X射线

期刊

氮化铝磁控反应溅射择优取向纯氮气AlN Magnetron reactive sputtering Preferred orientation Pure

铸态C72500合金组织与性能分析

本文研究了C72500铸态铜合金引线框架材料的微观组织和性能,得出抗拉强度达到250MPa,延伸率为16.851%,断面收缩率达到8.75%.说明铸态的C72500合金具有良好的抗拉性能和良好的

期刊

引线框架材料铸造铜合金Lead - frame material Casting Copper alloy