互连网络的路径限长问题

摘要

路径长度限制问题是图论中的Menger定理的变形和推广,在实时容错网络设计和分析中有重要意义.该文研究此问题,并得到如下结果:1.对于给定的正整数d,A<,d>(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数;B<,d>(D)表示D的顶点集B中的最小顶点数使得D-B的直戏大于d.已证明确定A<,d>(D)的问题是NPC问题,而且显然有不等式A<,d>(D)≤B<,d>(D).该文考虑D为超立方体网络、De Bruijn网络和Kautz网络,对d的不同值确定了A<,d>(D)及B<,d>(D),而且有A<,d>(D)=B<,d>(D).2.讨论一般有向图的路径限长问题,将无向图的关于路径限长问题的几个著名结果推广至有向图;

目录

摘要

ABSTRACT

第一章引言

§1.1基本的图论概念

§1.2路径限长问题

第二章几个著名网络的路径限长问题

§2.1 n维超立方体网络

§2.2 De Bruijn网络

§2.3 Kautz网络

§2.4结束语

第三章有向图的路径限长问题

§3.1引言

§3.2主要结果

§3.3结束语

参考文献

99年9月至2002年7月完成的论文

致谢