树的费用全染色的近似算法

来源 :山东大学学报：理学版 | 被引量 : 0次 | 上传用户：daney_he

【摘要】

：

给定无向简单图G=（V，E）与颜色集C，并且对C中的每一种颜色。设定一个费用值w（c）∈R^＊．全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色．定义了费用全染色

【作者】

：

陈勇

【机构】

：

山东大学数学与系统科学学院,济南大学理学院

【出处】

：

山东大学学报：理学版

【发表日期】

：

2006年1期

【关键词】

：

边染色全染色 NP-HARD 费用边染色费用全染色树 edge coloring total-coloring NP-hard cost edge-

【基金项目】

：

国家自然科学基金资助项目（10271065）,致谢：对李国君教授的精心指导表示衷心感谢,特别感谢吴建良副教授在染色方面的指导,井提供相关的文献资料.

下载到本地 , 更方便阅读

下载此文赞助VIP

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

论文部分内容阅读

给定无向简单图G=（V，E）与颜色集C，并且对C中的每一种颜色。设定一个费用值w（c）∈R^＊．全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色．定义了费用全染色问题，即求解最优的全染色f，使得染色费用和x∈v（c）JE（G）w（f（x））最小，时于树图T，给出了一个2-近似算法，该算法的运行时间为O（nΔ^2）．

其他文献

对行政事业单位内部审计的思考

内部审计是单位经济监督的重要组成部分，在经济发展的大潮中发挥着举足轻重的作用，许多企业纷纷将内审做为管理改革重点，然而，大部分行政事业单位内部审计工作仍存在无机构、无人

期刊

行政事业单位内部审计

一类非线性系统的自适应模糊滑模控制

针对一类不确定非线性系统提出了一种自适应模糊控制方法.该方法用模糊逻辑系统(FLS)逼近理想控制器;用滑模补偿控制器(SMCC)全局补偿逼近误差和系统的不确定性并消除外部干

期刊

非线性系统自适应模糊滑模控制模糊逻辑系统稳定性分析nonlinear systemadaptive fuzzy slide controlfuzzy

价值观对大学生就业选择的影响机制研究

大学生的价值观正处于逐步形成的阶段，根据实际情况需要对大学生的价值观进行实际认定。认定过程总需要结合每一个人的实际情况，分析每一个人的生活环境、教育水平、社会经济以

期刊

价值观大学生就业

幽默效果的语境制约

幽默效果的产生不仅取决于幽默文本,而且受到语境的制约.本文分别从表达者的角色及场合、心理距离的控制、接受者的个体差异、时代民族的文化背景四个层面加以总结和分析,探

期刊

幽默效果语境制约

园林绿化与经济发展关系探究

根据唯物主义普遍联系的观点，园林绿化事业与社会经济发展之间存在一定程度的辩证关系。概括而言。经济发展是园林绿化事业不断向前迈进的物质基础，而同时，城市园林绿化事业的发

期刊

园林绿化经济发展辩证关系协同发展

大学生诚信缺失现象及其教育

大学生作为将来国家建设的主体,他们的诚信缺失不仅会影响其本身的前途,更会给国家建设造成不可估量的损失.对大学生诚信缺失的表现进行分析,针对这些现象采取相应的措施,建

期刊

大学生诚信教育college students honesty and credit education

论工程项目风险管理

在工程项目管理过程中,正确分析与识别项目存在的风险因素,并采取科学的风险控制对策,是项目风险管理的重要内容,也是确保项目目标实现的前提和保证.

期刊

工程项目风险管理控制对策

事业单位人力资源战略管理分析

改革开放以来，我国的事业单位为了跟上社会经济发展的步伐，进行了一系列改革。本文就对事业单位人力资源的战略管理进行了分析，给出了一些作者自己的看法。

期刊

事业单位人力资源战略管理

浅析新形势下党风廉政建设责任制的现实意义

党风廉政建设责任制对于强化各级领导班子和领导干部抓反腐倡廉建设的政治责任，保证党中央、国务院关于党风廉政建设和反腐败斗争各项决策部署的贯彻落实，进一步提高管党治党水

期刊

党风廉政建设责任制反腐倡廉意义

言论：程默：“土地财政”不变房价难降

安信咨询公司分析师程默日前撰文表示，中国的房地产市场早已不是一个单纯的市场问题。对很多地方政府来讲，土地出让金已经成为重要的收入来源。据统计，2007年房地产商交给政府的

期刊

土地出让金财政总收入房价言论地方政府房地产市场咨询公司市场问题

树的费用全染色的近似算法

与本文相关的学术论文