摘要:

AbstractA lower plane for the network design problem is a linear lower approximation of the objective function and is used to obtain a lower bound in the branch and bound algorithm. In this article, we derive two new lower planes for the network design problems through combinatorial arguments. The first lower plane is of complexityO(n4) and produces a lower bound which is sharper than those of existing lower planes. The second lower plane is of complexityO(n3) and produces a reasonably good lower bound. Computational results are presented comparing the bounds obtained by the new lower planes with those of the existing lower planes.

ISSN:0028-3045    

DOI:10.1002/net.3230170202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

摘要:

AbstractThe problem of determining a minimum cost connected network (i.e., weighted graph)Gthat spans a given subset of vertices is known in the literature as the Steiner problem in networks. We survey exact algorithms and heuristics which appeared in the published literature. We also discuss problems related to the Steiner problem in networks.

ISSN:0028-3045    

DOI:10.1002/net.3230170203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

摘要:

AbstractConsider an undirected networkGwith node setVand arc setE= {1, …,n} where arcs fail randomly and independently. LetTbe a subset ofVand letMkdenote the number of ways that all the nodes ofTare connected (T‐connectivity) with exactlykoperating arcs andn‐kfailed arcs. This paper describes a sampling plan for estimating {Mk} and linear functions of these parameters, including theT‐connectedness reliability functiong(p) for common failure probability 1 ‐p. Point and simultaneous interval estimates are derived for {Mk/( kn}, where the interval estimates meet a fixed width criterion inO(nlogn) time as the size of the networkngrows. Whereas all previously proposed Monte Carlo sampling plans enable one to estimateg(p) for a fixedp, the proposed method allows one to estimate the entire function {g(p),p∈P}, where eitherP=P*= {qi: O ≦qi≦ 1, 1 ≦i= ≦v} orP=P**= {[a,b]: 0 ≦a≦b≦ 1}. HereP*denotes a finite set of points in [0, 1] andP**an interval in [0, 1]. Simultaneous interval estimates are derived that meet a fixed width criterion inO(n) time forP=P*and inO(n2) time forP=P**asn→ ∞. Aprioribounds are also derived forg(p) and it is shown how these can be used to give guidance on the performance of the sampling plan. An example based on a network with 44 nodes and 85 arcs

ISSN:0028-3045    

DOI:10.1002/net.3230170204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

摘要:

AbstractStore‐and‐forward communication networks may be designed so as to be free from store‐and‐forward deadlock. This is accomplished by incorporating in the network an acyclic buffer graph on which messages are forwarded, from buffer to buffer, according to all the desired routes. A technique producing minimum buffer graphs for a rather large class of networks is illustrated. Successively, a comparison is made with other well‐known deadlock avoidance techniques, showing that substantial savings can be

ISSN:0028-3045    

DOI:10.1002/net.3230170205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

摘要:

AbstractThe theory of directed switching networks is developed. After the fundamental concepts are defined, the rank of the path matrix of a Directed Single‐Contact (Di‐SC) network is discussed. The theorem which gives the essential relationship between the SC and Di‐SC networks is proved. Then the Odd‐Addition‐Subtraction (OAS) condition is given as a necessary condition for Di‐SC functions. The analysis of directed switching networks and the synthesis of Di‐SC networks are also given for practical applications. The results could be used in the design of electrical and computer systems with dire

ISSN:0028-3045    

DOI:10.1002/net.3230170206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

摘要:

AbstractCut set inclusion and exclusion is a well known reliability evaluation procedure. However, many of the cut set intersection terms cancel so it can be laborious to use. In directed graphs it is shown that the number of noncancelling terms cannot exceed the number of possible ordered partitions of the set of nodes. The resulting node partition formula will still contain cancelling terms when applied to incomplete graphs. An algorithm is developed to determine the set of noncancelling terms and its application illustrated on some special classes of graphs: acyclic graphs and graphs admitting a modular decomposition.

ISSN:0028-3045    

DOI:10.1002/net.3230170207

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

摘要:

AbstractIn [G. Gunther, Neighbor‐connectivity in regular graphs.Discrete Appl. Math.11(1985) 233–243] Gunther introduced the concept of akneighbor‐connected graph, which has the property that the removal of anyk− 1 closed neighborhoods neither disconnects the graph, nor leaves only a complete graph. In this paper we pursue the investigation of minimal graphs that arek‐regular in addition to beingkneighbor‐connected. In a private communication, Gunther conjectured that ifGis such a graph which contains no cliques of size larger thanm, then |V(G)| ≧k2+ (k+ 1 −m) (k− 1) + 1. In the above reference, he proved that this conjecture is valid in the case thatm=kand characterized the minimal graphs. In this paper, we begin to investigate the case wherem= 2. We give some results connecting the minimal graphs to other comb

ISSN:0028-3045    

DOI:10.1002/net.3230170208

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230170201

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1987

数据来源: WILEY