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

李学良; 涂建华

首页> 中文期刊> 《新疆大学学报：自然科学版(中英文)》 >次模函数近似算法求最小颜色生成树(英文)

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《新疆大学学报：自然科学版(中英文)》 |2008年第4期|391-394|共4页
作者
李学良; 涂建华;
展开▼
作者单位

南开大学组合数学中心;

展开▼
原文格式 PDF
正文语种 chi
中图分类图论;
关键词
边着色图; 最小颜色生成树(MCST); 最大颜色匹配(MCM); 次模函数; 近似算法;

相似文献

中文文献
外文文献
专利

1. 次模函数近似算法求最小弱顶点覆盖 [J] . 涂建华 ,高昊宇 ,赖文华 . 北京化工大学学报（自然科学版） . 2011,第001期
2. 求一类上模集函数最小值问题的近似算法及性能保证 [J] . 张防防 ,王武民 ,柘晓莉 . 兰州交通大学学报 . 2008,第003期
3. 最大化非减次模集函数问题的近似算法及其性能保证 [J] . 郝自军 ,何尚录 . 西南民族大学学报（自然科学版） . 2009,第001期
4. 最小度生成树的一种近似算法 [J] . 申玉红 . 大学数学 . 2013,第001期
5. 有向无环图最小度生成树问题的一种近似算法 [J] . 姚国辉 ,朱大铭 ,马绍汉 . 计算机研究与发展 . 2009,第006期
6. 内点带权的最小生成树的近似算法 [C] . 王海涛 ,李建 ,葛启 . 2005年全国理论计算机科学学术年会 . 2005
7. 带线性/次模惩罚的次模边覆盖问题的近似算法 [A] . 王鑫 . 2021

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

摘要

著录项

相似文献

相关主题

期刊订阅