树状网络上k-tree center问题

• 作者: 刘建贞 杨建芳
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 树中心问题 树收缩 控制
• 年，卷（期）: 2009,（3）
• 页码范围: 76-79
• 页数: 4页
• 分类号: TP393.01
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2009.03.020

摘要

树状网络上的k-tree center问题是指在树上选择一棵叶子数恰好为k的子树,使得树上其他节点到该子树的最大距离最小化.由于center问题的目标函数是满足最大距离最小化,如果S是问题的最优解,则S肯定包含树的中心,因此在求解k-tree center问题时,首先找到树的中心,然后从中心出发,利用树收缩的思想逐步找到满足要求的子树.该文基于此对该问题给出了时间复杂度为O(kn)的多项式时间算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨建芳	杭州市电子科技大学运筹与控制研究所	2	0	0.0	0.0
2	刘建贞	杭州市电子科技大学运筹与控制研究所	2	0	0.0	0.0