最小最大树划分的近似算法与最小和树划分的精确算法

农庆琴; 原晋江

首页> 中文期刊> 《运筹学学报》 >最小最大树划分的近似算法与最小和树划分的精确算法

最小最大树划分的近似算法与最小和树划分的精确算法

开具论文收录证明 >>

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

文献代查 >>

页面导航

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

摘要

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题).文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法.

著录项

来源
《运筹学学报》 |2006年第4期|115-121|共7页
作者
农庆琴; 原晋江;
展开▼
作者单位

郑州大学数学系,郑州,450052;

郑州大学数学系,郑州,450052;

展开▼
原文格式 PDF
正文语种 chi
中图分类运筹学;
关键词
运筹学; 划分; 支撑树; 多项式时间算法; 近似算法;

相似文献

中文文献
外文文献
专利

1. 基于最小聚类划分的K-means聚类(1+ε)近似算法 [J] . 王守强 ,朱大铭 ,史士英 . 计算机研究与发展 . 2008,第0z1期
2. 最小—最大圈划分的近似算法 [J] . 邱保建 ,李敏 ,刘坚 . 山东大学学报：理学版 . 2005,第6期
3. 结合最小生成树划分的高分遥感图像分割 [J] . 林文杰 ,李玉 ,赵泉华 . 遥感信息 . 2018,第006期
4. 一种基于聚类融合和最小生成树的重叠社交网络划分方法 [J] . 高博 ,王丽娜 ,李力 . 机床与液压 . 2017,第024期
5. 最小方差在农业类型(或农业区)划分中的应用——以我国粮食作物结构类型划分为例 [J] . 张耀光 . 经济地理 . 1986,第1期
6. 基于最小聚类划分的K-means聚类(1+ε)近似算法 [C] . 王守强 ,山东交通学院信息工程系 ,朱大铭 . 2007全国理论计算机科学学术年会 . 2007
7. 关于最小—最大圈划分的近似算法 [A] . 邱保建 . 2003

最小最大树划分的近似算法与最小和树划分的精确算法

摘要

著录项

相似文献

相关主题

期刊订阅