| 按信包传递最小普查图研究 |
| |
| 引用本文： | 黄振杰. 按信包传递最小普查图研究[J]. 计算机学报, 1995, 18(10): 737-743 |
| |
| 作者姓名： | 黄振杰 |
| |
| 作者单位： | 漳州师范学院数学系 |
| |
| 摘 要： | 普查是信息网络中结点之间的一种常见的也是重要的信息传递方式，在普查过程中，网络所有结点的信息按一定的约束条件传递到终结点。本文定义并讨论了按信包传递最小普查图ｐ－ｍｅｇ，给出了最小普查时间ｔｐ（ｎ）的公式，在讨论了最小普查图与最小广播图的关系之后，指出了识别一个图是否为最小普查图的问题是ＮＰ完全问题，而且对ｐ＝１，２，３完全解决了ｐ－ｍｅｇ的构造问题，对ｐ＝２＾ｋ给出ｎ＝ｍ．２＾ｋ时ｐ－ｍｅｇ的构
|
| 关 键 词： | 最小普查图 网络 信息网络 拓扑结构 图 |
MINIMUM CENSUS GRAPH BY PACKET OF SIZE p |
| |
| Huang Zhenjie. MINIMUM CENSUS GRAPH BY PACKET OF SIZE p[J]. Chinese Journal of Computers, 1995, 18(10): 737-743 |
| |
| Authors: | Huang Zhenjie |
| |
| Abstract: | Census taking is a message propagation process over a network whereby all the messages in the network have to be received at a particular unit.This paper defines and studies the minimum census graph by packet of size p(p-mcg)and presents the formula of minimum census taking time tp,(n). The relation between the minimum broadcast graph and the minimum census graph is discussed and the problem of recognizing whether a given graph is a p-mcg is proved to be NP-complete.Furthermore,some construction methods for p-mcg with p=1,2,3 and p=2k when n=m.2k is presented. |
| |
| Keywords: | Census taking minimum census graph network. |
| 本文献已被 CNKI 维普 等数据库收录！ |
