摘要:网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点。所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数)。假定每一次广播的执行时间为一单位,网络G的广播过程是广播的时间安排,使所有结点均获得消息。最优广播问题是求总时间最少的广播过程,在G是树网络情形,文献中已给出时间界为O(n^2)的算法,本文给出线性时间的简捷算法。
关键词:组合优化 网络广播 树网络 线性算法
单位:河南工业大学理学院; 河南郑州450052; 河南工业大学国际学院; 河南郑州450052
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社