运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2003年
1期
59-64
,共6页
路,Menger定理,超立方体网络,De Bruijn网络,Kautz网络
路,Menger定理,超立方體網絡,De Bruijn網絡,Kautz網絡
로,Menger정리,초립방체망락,De Bruijn망락,Kautz망락
paths%Menger's theorem%hypercubes%de Bruijn digraphs%Kautz digraphs
设给出了(h,ψ)-η限长路径问题是图论中的Menger定理的变形和推广,在实时容错网络设计和分析中有重要意义.对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数;Bd(D)表示D的顶点子集B中的最小顶点数使得D-B的直径大于d.已证明确定Ad(D)的问题是NPC问题,而且显然有不等式Ad(D)≤Bd(D).本文考虑D为超立方体网络、De Btuijn网络和Kautz网络,对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D).
設給齣瞭(h,ψ)-η限長路徑問題是圖論中的Menger定理的變形和推廣,在實時容錯網絡設計和分析中有重要意義.對于給定的正整數d,Ad(D)錶示網絡D中任何距離至少為2的兩頂點之間內點不交且長度都不超過d的路的最大條數;Bd(D)錶示D的頂點子集B中的最小頂點數使得D-B的直徑大于d.已證明確定Ad(D)的問題是NPC問題,而且顯然有不等式Ad(D)≤Bd(D).本文攷慮D為超立方體網絡、De Btuijn網絡和Kautz網絡,對d的不同值確定瞭Ad(D)及Bd(D),而且均有Ad(D)=Bd(D).
설급출료(h,ψ)-η한장로경문제시도론중적Menger정리적변형화추엄,재실시용착망락설계화분석중유중요의의.대우급정적정정수d,Ad(D)표시망락D중임하거리지소위2적량정점지간내점불교차장도도불초과d적로적최대조수;Bd(D)표시D적정점자집B중적최소정점수사득D-B적직경대우d.이증명학정Ad(D)적문제시NPC문제,이차현연유불등식Ad(D)≤Bd(D).본문고필D위초립방체망락、De Btuijn망락화Kautz망락,대d적불동치학정료Ad(D)급Bd(D),이차균유Ad(D)=Bd(D).
The problem of paths with bounded length, being a variation and a generalization of Menger's theorem, is of very important significance in the design and analysis of real-time or fault-tolerant interconnection networks. For a given positive integer d, the symbol Ad(D) denotes the maximum number of internally disjoint paths of length at most d between any two vertices with distance at least two in the network D; the symbol Bd(D) denotes the minimum number of vertices whose deletion results in diameter larger than d. Obviously, Ad(D) ≤ Bd(D) and it has been shown to determine the value of Ad(D) is NP-complete. In the present paper, three well-known networks, hypercubes, de Bruijn and Kautz, are considered and the values of Ad(D) and Bd(D) are determined, which show Ad(D) = Bd(D).
