| 树网络上f模式最优广播问题的线性算法 |
| |
| 引用本文： | 林浩,赵洁.树网络上f模式最优广播问题的线性算法[J].经济数学,2006,23(1):84-88. |
| |
| 作者姓名： | 林浩 赵洁 |
| |
| 作者单位： | 河南工业大学理学院,河南,郑州,450052;河南工业大学国际学院,河南,郑州,450052 |
| |
| 基金项目： | 国家自然科学基金;河南工业大学校科研和教改项目 |
| |
| 摘 要： | 网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.
|
| 关 键 词： | 组合优化 网络广播 树网络 线性算法 |
| 修稿时间： | 2005年5月19日 |
A LINEAR-TIME ALGORITHM FOR THE f-TYPE OPTIMAL BROADCAST PROBLEM IN TREE NETWORKS |
| |
| Lin Hao,Zhao Jie.A LINEAR-TIME ALGORITHM FOR THE f-TYPE OPTIMAL BROADCAST PROBLEM IN TREE NETWORKS[J].Mathematics in Economics,2006,23(1):84-88. |
| |
| Authors: | Lin Hao Zhao Jie |
| |
| Abstract: | A broadcast at a node v of network G is to send a message from it to some of adjacent nodes.An(f-type) broadcast is that each node v sends the message to at most f(v) adjacent nodes in a broadcast(where f is a given integer-value function).Assume that the performance time of each broadcast is unit.The broadcast process is a schedule of broadcasts such that all nodes can receive the message.The optimal broadcast problem is to find a broadcast process with the minimum total performance time.When G is a tree network,there has been an O(n~2) time algorithm in the literature.This paper presents a simplified algorithm with linear time bound. |
| |
| Keywords: | Combinatorial optimization network broadcast tree network linear algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
