k-tree core problem with degree constraint in tree network

doi:10.3778/j.issn.1002-8331.2009.34.013

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (34): 41-43.DOI: 10.3778/j.issn.1002-8331.2009.34.013

• 研究、探讨 • Previous Articles Next Articles

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

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

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

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

通讯作者: 杨建芳

Abstract

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

摘要： 考虑到在实际应用中，由于计算机和通信网络中一般每个设备的处理能力是有限的，在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问题, 动态规划, 局部根核, 贪婪思想

CLC Number:

O157.5

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.

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

[1]	ZHOU Ruimin, LI Hui. Path Planning of Mobile Robot Based on Improved Dynamic Programming Algorithm [J]. Computer Engineering and Applications, 2020, 56(21): 20-24.
[2]	CHEN Junjie, TONG Shurong, NIE Yafei, ZHANG Jingwen. R&D Program Scheduling and Staff Assignment with Hierarchical Levels of Competency [J]. Computer Engineering and Applications, 2019, 55(3): 209-218.
[3]	LIAN Wei. Globally Optimal Shape Matching Algorithm Using Tree Representation [J]. Computer Engineering and Applications, 2019, 55(1): 217-225.
[4]	ZHANG Yu, CUI Yaodong, LIANG Zehua. Two-dimensional cutting stock problem of multiple logs [J]. Computer Engineering and Applications, 2018, 54(19): 266-270.
[5]	XIAO Hongde. Calculation of minimum count of money and determination of money denomination [J]. Computer Engineering and Applications, 2018, 54(16): 266-270.
[6]	SUN Peishuang, HAN Qirui. Improved optimal stitching line applied to image stitching [J]. Computer Engineering and Applications, 2016, 52(21): 218-221.
[7]	FANG Gang1, ZHANG Shemin2. 3-gram statistical language model optimization to expression vector design [J]. Computer Engineering and Applications, 2016, 52(15): 60-64.
[8]	ZHANG Xingong, WANG Hui, BAI Shikun. Two-agent scheduling on single machine to minimize number of tardy jobs [J]. Computer Engineering and Applications, 2016, 52(14): 32-36.
[9]	LI Huiguang, LI Feng, SHAO Nuan, SHA Xiaopeng, WANG Shuai. Segment-based stereo matching method with ground control points [J]. Computer Engineering and Applications, 2015, 51(23): 160-163.
[10]	ZHANG Yu, XU Hongze, CHEN Jianqiang,ZHANG Luning. Research on optimization strategy of train route control in metallurgical enterprises [J]. Computer Engineering and Applications, 2015, 51(17): 250-254.
[11]	SHEN Lu1，2, JI Yun1, JI Dongbao3, LI Ping4. Pattern matching with variable length wildcards [J]. Computer Engineering and Applications, 2015, 51(15): 43-47.
[12]	WANG Jun. Dynamic programming and tabu search hybrid algorithm for Vehicle Routing Problem with fuzzy time windows [J]. Computer Engineering and Applications, 2014, 50(24): 58-64.
[13]	ZHAO Xu, WANG Wei. Optimization research of DSAMDP method with dynamic programming theory [J]. Computer Engineering and Applications, 2014, 50(22): 83-87.
[14]	ZENG Qiang1, SHEN Ling2, WU Liyun1, LAN Jianyi1. Improved method to optimize aggregate production planning based on dynamic programming [J]. Computer Engineering and Applications, 2014, 50(21): 248-253.
[15]	ZHAO Feng1, YANG Wei1，2，3, YANG Zhaoxu3, SUN Shaoshan3. UAV three-dimensional dynamic route planning and guidance control research [J]. Computer Engineering and Applications, 2014, 50(2): 58-64.

k-tree core problem with degree constraint in tree network

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics