树状网络上带度约束的k-tree core问题

doi:10.3778/j.issn.1002-8331.2009.34.013

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (34): 41-43.DOI: 10.3778/j.issn.1002-8331.2009.34.013

树状网络上带度约束的k-tree core问题

杨建芳¹，刘建贞¹，黄孙琴²

1.杭州电子科技大学理学院运筹与控制研究所，杭州 310018
2.浙江长征职业技术学院基础部，杭州 310023

收稿日期:2008-07-08 修回日期:2008-10-14 出版日期:2009-12-01 发布日期:2009-12-01
通讯作者: 杨建芳

k-tree core problem with degree constraint in tree network

YANG Jian-fang¹，LIU Jian-zhen¹，HUANG Sun-qin²

1.Institute of Operational Research & Cybernetics，Hangzhou Dianzi University，Hangzhou 310018，China
2.Zhejiang Changzheng Professional & Technical College，Hangzhou 310023，China

Received:2008-07-08 Revised:2008-10-14 Online:2009-12-01 Published:2009-12-01
Contact: YANG Jian-fang

摘要/Abstract

摘要： 考虑到在实际应用中，由于计算机和通信网络中一般每个设备的处理能力是有限的，在k-tree core问题的基础上，提出了同时带有度约束的k-tree core问题，即k-tree core中的每个节点在子树中的度不超过给定常数q，记为q-DTC（k）（Degree constrained Tree Core）。利用动态规划的方法，采用最优化原则先找出文中所定义的局部根核集，然后利用贪婪思想对不满足度限制的节点所在的分支加以删减，对无权树和赋权树得到了复杂度分别为O（kn）和O（max{n log n，kn}）多项式时间算法，其中n是树的节点数。

关键词: tree core问题, 动态规划, 局部根核, 贪婪思想

Abstract: According to background of actual application，the processing ability of each equipment is limited generally in the computer and correspondence networks.The article puts forward the k-tree core problem with degree constraint in a tree network，denoted as q-DTC（k）（Degree constrained Tree Core）.With the method of dynamic programming，adopting optimizing principle，it finds out local rooted cores.Then making use of greedy idea，the branch of node which is dissatisfied with degree constraint must be deleted.It takes O（kn） and O（max{n log n，kn}） time algorithm for unweighted tree and weighted tree.

Key words: tree core problem, dynamic programming, local rooted core, greed idea

中图分类号:

O157.5

杨建芳¹，刘建贞¹，黄孙琴². 树状网络上带度约束的k-tree core问题[J]. 计算机工程与应用, 2009, 45(34): 41-43.

YANG Jian-fang¹，LIU Jian-zhen¹，HUANG Sun-qin². k-tree core problem with degree constraint in tree network[J]. Computer Engineering and Applications, 2009, 45(34): 41-43.

[1]	周睿慜，李辉. 改进动态规划算法的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(21): 20-24.
[2]	陈俊杰，同淑荣，聂亚菲，张静文. 考虑胜任力水平的研发项目群人力资源调度[J]. 计算机工程与应用, 2019, 55(3): 209-218.
[3]	连玮. 采用树表示的全局最优形状匹配算法[J]. 计算机工程与应用, 2019, 55(1): 217-225.
[4]	张雨，崔耀东，梁泽华. 多尺寸圆木二维下料问题研究[J]. 计算机工程与应用, 2018, 54(19): 266-270.
[5]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[6]	孙培双，韩其睿. 彩色图像最优拼接线的改进算法研究[J]. 计算机工程与应用, 2016, 52(21): 218-221.
[7]	方刚1，张社民2. 三元统计语言模型对基因表达载体设计的优化[J]. 计算机工程与应用, 2016, 52(15): 60-64.
[8]	张新功，王慧，柏世坤. 最小化误工工件个数的两代理单机排序问题[J]. 计算机工程与应用, 2016, 52(14): 32-36.
[9]	李惠光，李峰，邵暖，沙晓鹏，王帅. 基于图像分割和控制点的立体匹配算法研究[J]. 计算机工程与应用, 2015, 51(23): 160-163.
[10]	张昱，徐洪泽，陈建强，张鹿宁. 冶金企业内部铁路进路控制优化策略研究[J]. 计算机工程与应用, 2015, 51(17): 250-254.
[11]	沈璐1，2，纪允1，纪冬宝3，李萍4. 带可变长度通配符的模式匹配算法[J]. 计算机工程与应用, 2015, 51(15): 43-47.
[12]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.
[13]	王君. 模糊时间窗VRP的动态规划和禁忌搜索混合算法[J]. 计算机工程与应用, 2014, 50(24): 58-64.
[14]	赵旭，王伟. 动态规划理论在DSAMDP方法中的优化研究[J]. 计算机工程与应用, 2014, 50(22): 83-87.
[15]	曾强1，沈玲2，吴立云1，兰建义1. 一种改进的综合生产计划动态规划优化方法[J]. 计算机工程与应用, 2014, 50(21): 248-253.

树状网络上带度约束的k-tree core问题

k-tree core problem with degree constraint in tree network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics