首页 | 本学科首页   官方微博 | 高级检索  
     检索      

按信包传递最小普查图研究
引用本文:黄振杰.按信包传递最小普查图研究[J].计算机学报,1995,18(10):737-743.
作者姓名:黄振杰
作者单位:漳州师范学院数学系
摘    要:普查是信息网络中结点之间的一种常见的也是重要的信息传递方式,在普查过程中,网络所有结点的信息按一定的约束条件传递到终结点。本文定义并讨论了按信包传递最小普查图p-meg,给出了最小普查时间tp(n)的公式,在讨论了最小普查图与最小广播图的关系之后,指出了识别一个图是否为最小普查图的问题是NP完全问题,而且对p=1,2,3完全解决了p-meg的构造问题,对p=2^k给出n=m.2^k时p-meg的构

关 键 词:最小普查图  网络  信息网络  拓扑结构  

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 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号