论文部分内容阅读
网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点。所谓f模式广播，是指结点v在一次广播中至多向f（v）个相邻结点传递信息（f为给定的整值函数）。假定每一次广播的执行时间为一单位，网络G的广播过程是广播的时间安排，使所有结点均获得消息。最优广播问题是求总时间最少的广播过程，在G是树网络情形，文献中已给出时间界为O（n^2）的算法，本文给出线性时间的简捷算法。