Necessary and sufficient conditions for Logd(N,m,p) network to be point-to-point strictly nonblocking are known. Recently, Kabacinski and Danilewicz obtained necessary and sufficient conditions for the Log2(N,0,p) network to be broadcast strictly nonblocking. In this paper, we give necessary and sufficient conditions for Logd(N,m,p) to be f-cast strictly nonblocking for every f, thus covering the point-to-point case (f=1) and the broadcast case (f=N) as special cases

For the multicast rearrangeable 3-stage Clos networks where input crossbars do not have fan-out capability, Kirkpatrick, Klawe, and Pippenger gave a sufficient condition and also a necessary condition which differs from the sufficient condition by a factor of 2. In this paper, we first tighten their conditions. Then we propose a new necessary condition based on the affine plane such that the necessary condition matches the sufficient condition for an infinite class of 3-stage Clos networks.

Equivalence of multistage interconnection networks is an important concept because it reduces the number of networks to be studied. Equivalence among the banyan networks has been well studied. Occasionally, the study was extended to networks obtained by concatenating two banyan networks (identifying the output stage of the preceding network with the input stage of the succeeding one). Recently, equivalence among the class of networks that are obtained from banyan networks by adding extra stages has also been studied. Note that all these above-mentioned networks are in the general class of buddy networks. In this article we study equivalence of buddy networks with an arbitrary number of stages. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(4), 171–176 2005

We give necessary and sufficient conditions for the d-nary multilog network to be strictly nonblocking under the discrete multirate model, and we give sufficient conditions for the same under the continuous multirate model.

The 3-stage Clos network is the most-studied switching network. However, exact conditions on the strictly nonblocking multicast three-stage Clos network under various models are difficult to get, due to the messy detail and because each case employs a different argument. Hwang and Liaw (2000) made the latest attempt and pointed out errors in previous attempts. However, they made errors, too. In this paper, we propose a unifying approach to study those models systematically (which also applies to some wide-sense nonblocking (WSNB) networks). We also propose a new routing algorithm, and use the unifying approach to derive a necessary and sufficient condition for WSNB.

We extend previous results on sufficient conditions for rearrangeable Log/sub 2/(N,m,p) networks to Log/sub d/(N,m,p) networks. We show that the original argument using path-intersecting graphs cannot be extended to d>2, and we give a new argument. Further, we show our sufficient conditions are also necessary.

An importance index measures the relative importance of a component in comparison to other components with respect to the system reliability. We survey many importance indices proposed in the literature, and some new ones of our own, to show how they relate. Our results can be used in two situations: 1) When components are functionally interchangeable, then more reliable units should go to the more important components. 2) When there is a fixed budget to improve the system reliability, the more important components should get first attention if everything else is equal.

In the 1-rate(f) network, each link can carry up to f messages for some integer f. The classical model is the special case when f=1. We show that a network is strictly nonblocking under the 1-rate(f) model if and only if it is strictly nonblocking under the classical model.

We study optimization problems over partitions of the finite set N = {1,...,n}, where each element i in the partitioned set N is associated with a real number $\theta^i$ and the objective associated with a partition $\pi=(\pi_1, \ldots,\pi_p)$ has the form $F(\pi)=f(\theta_{\pi})$, where $ \theta_{\pi} = (\sum _{i\in{\pi_1}}\theta^i,\ldots, \sum _{i\in\pi_{p}}\theta^i)$. When F is to be either maximized or minimized, we obtain conditions that allow for simple constructions of partitions that are uniformly optimal for all Schur convex functions f.

Abstract The graph representation G(M) of a multistage switching network M is well known. Lea IEEE Trans Commun 38 (1990), 529–538 observed that link‐disjoint paths in M correspond to node‐disjoint paths in G(M). He proposed G(M) as a network by treating nodes as crossbars to transfer the node‐disjoint property to the crosstalk‐free property essential for photonic networks using directional couplers as components. However, such a network has its peculiarities and is not commonly used. In this paper, we will show how to take advantage of this correspondence to construct nonblocking crosstalk‐free networks using the vertical stacking method. Our construction simplifies the proofs of many existing results, as well as establishing some new results. © 2003 Wiley Periodicals, Inc.

Recently, Tscha and Lee proposed a fixed-size window algorithm for the multicast Log/sub 2/(N,0,p) network and expressed a desire to see its extension to the Log/sub 2/(N,m,p) network. Later, Kabacinski and Danilewicz generalized the fixed-size window to variable size to improve the results. In this paper, we further extend the variable-size results from the Log/sub 2/(N,0,p) network to Log/sub 2/(N,m,p). Note that this extension is difficult since each link in the channel graph of Log/sub 2/(N,0,p) has the same blocking effect, but not so in Log/sub 2/(N,m,p). We also determine the optimal window size and optimal m.

F.K. Hwang and S.C. Liaw (see IEEE/ACM Trans. Networking, vol.8, p.535-9, 2000) introduced a new nonblocking requirement for 2-cast traffic which imposes different requirements on different types of coexisting calls. The requirement is strictly nonblocking for point-to-point calls among the 2-cast traffic, and is rearrangeable for genuine 2-cast calls. We generalize the 2-cast calls to multicast calls and give a sufficient condition for such networks when the number of multicast calls is upper bounded.

A cyclic consecutive-k-out-of-n: G system consists of n components lying on a cycle. Those components are exchangeable but may have different working probabilities. The system works if and only if there are k consecutive components at work. What is the optimal assignment of components for maximizing the reliability of the system? Does the optimal assignment depend on the working probability values of components? For $k \leq n \leq 2k+1$, Zuo and Kuo in 1990 proposed a solutionindependent from the working probability values of components, called the invariant optimal assignment. However, their proof is incomplete, pointed out recently by Jalali et al. [The Optimal Consecutive-k-out-of-n: G Line for $n \leq 2k$}, manuscript, 1999]. We present a complete proof in this paper.

Abstract A bit permutation network is an s‐stage interconnection network composed of dn−1 d × d crossbar switches in each stage. This class of networks includes most of the multistage interconnection networks. Recently, Chang et al. [Networks 33 (1999), 261–267] showed that an s‐stage d‐nary bit permutation network N with dn inputs (outputs) can be characterized by an (s − 1)‐vector (k1, …, ks−1), where kt ∈ {1, …, n − 1}. In this paper, we give a simple (but not trivial) formula to determine the characteristic vector of a new network G(N)+, which is, approximately, the line digraph of N. We use this formula to obtain relations between some well‐studied bit permutation networks. © 2001 John Wiley & Sons, Inc.

The combinatorial group testing problem is, assuming the existence of up to d defectives among n items, to identify the defectives by as few tests as possible. In this paper, we study the problem for what values of n, given d, individual testing is optimal in nonadaptive group testing. Let N(d) denote the largest n for fixed d for which individual testing is optimal. We will show that N(d)=(d+1) 2 under a prevalent constraint in practical nonadaptive algorithms and prove that N(d)=(d+1) 2 for d=1, 2, 3, 4 without any constraint.

The goal of the fault diagnosis agreement (FDA) problem is to make each fault-free processor detect/locate a common set of faulty processors. The problem is examined on processors with mixed fault model (also referred to as hybrid fault model). An evidence-based fault diagnosis protocol is proposed to solve the FDA problem. The proposed protocol first collects the messages which have accumulated in the Byzantine agreement protocol as the evidence. By examining the collected evidence, a fault-free processor can detect/locate which processor is faulty. Then, the network can be reconfigured by removing the detected faulty processors and the links connected to these processors from the network. The proposed protocol can detect/locate the maximum number of faulty processors to solve the FDA problem.

We give necessary and sufficient conditions for strictly nonblocking three-stage Clos (1953) networks with two types of multicast traffic. Then, we extend the results to other models where the routing is under certain restrictions. Finally, we compare our results with existing literature to mark the differences and similarities.

In recent years, many multistage interconnection networks using 2 × 2 switching elements have been proposed for parallel architectures. Typical examples are baseline networks, banyan networks, shuffle-exchange networks, and their inverses. As these networks are blocking, such networks with extra stages have also been studied extensively. These include Benes networks and Δ ⊕ Δ′ networks. Recently, Hwang et al. studied k-extra-stage networks, which are a generalization of the above networks. They also investigated the equivalence issue among some of these networks. In this paper, we studied a more general class of networks, which we call (m + 1)-stage d-nary bit permutation networks. We characterize the equivalence of such networks by sequence of positive integers. © 1999 John Wiley & Sons, Inc. Networks 33: 261–267, 1999

Since Clos gave the first construction of a strictly nonblocking multistage interconnection network, only a few other constructions have been proposed in almost a half-century. In this paper, we introduce a constructive class of networks which utilizes crossbars of virtually any size and for which the sizes can vary from stage to stage. The interconnection between stages is a generalized shuffle pattern. We derive sufficient conditions for strictly nonblocking operation and suggest the potential for wide application of these networks by providing several special case results. © 1999 John Wiley & Sons, Inc. Networks 33: 269–291, 1999

We present the problem of constructing roads of minimum total length to interconnect n highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a set of optimality conditions for the problem and show how to construct a solution to meet this set of optimality conditions.

In the multirate switching environment each (connection) request is associated with a bandwidth weight. We consider a three-stage Clos network and assume that each link has a capacity of one (after normalization). The network is rearrangeable if for all possible sets of requests such that each input and output link generates a total weight not exceeding one, there always exists a set of paths, one for each request, such that the sum of weights of all paths going through a link does not exceed the link capacity. The question is to determine the minimum number of center switches which guarantees rearrangeability. We obtain a lower bound of 11n/9 and an upper bound of 41n/16. We then extend the result for the three-stage Clos network to the multistage Clos network. Finally, we propose the weighted version of the edge-coloring problem, which somehow has escaped the literature, associated with our switching network problem.

We extend the log/sub 2/ (N, m, P) network proposed by Shyy and Lea (1991) to base k. We give a unifying proof (instead of three separate cases as done by Shyy and Lea) for the condition of being strictly nonblocking, and a simpler expression of the result. We compare the number of crosspoints for log/sub k/(N, m, p) over various k.

We consider the problem of partitioning the vertex-set of a tree to p parts to minimize a cost function. Since the number of partitions is exponential in the number of vertices, it is helpful to identify small classes of partitions which also contain optimal partitions. Two such classes, called consecutive partitions and nested partitions, have been well studied for the set partition problem, which is a special case of the tree-partition problem when the tree is a path. We give conditions on the optimality of these classes on tree partitions and also extend our results to tree networks. © 1997 John Wiley & Sons, Inc. Networks 30: 75–80, 1997

A double-loop network with hop constants h1, h2, DL(n, h1, h2) may be represented as a directed graph with n nodes 0, 1, …, n − 1 and 2n links of the form i → i + h1mod n and i → i + h2mod n (referred to as h1-links and h2-links). They have been proposed as architectures for local area networks and for data alignment in SIMD processors, among other applications. Three reliability models of double-loop networks have been studied in the literature. In the link model, nodes always work and each link fails independently with probability p. Hwang and Li showed that for p small DL(n, 1, 1 + n/2) is most reliable for n even, and DL(n, 1, 2) is most reliable for n odd. In the node model, links always work and each node fails independently with probability p. Hu et al. showed that for p small DL(n, 1, 1 + ⌈n/2⌉) is the most reliable. However, no nonenumerative algorithms were given to compute the reliabilities of these most reliable networks except DL(n, 1, 1 + n/2) for even n under the node model. Recently, Hwang and Wright proposed a novel approach to compute the reliabilities of double-loop networks under the uniform model that each node fails with probability p, each h1-link with probability p1, and each h2-link with probability p2, and the failures are independent. In particular, they obtained the reliabilities for DL(n, 1, 2). In this paper, we applied their approach to compute the reliabilities of DL(n, 1, 1 + ⌈n/2⌉) under the uniform model, except that for n odd we need the assumption that h1-links always work. Note that even under this additional assumption our reliability model is more general than is the node model, the original model under which DL(n, 1, 1 + ⌈n/2⌉) is found to be most reliable for n odd. We also used this approach to obtain the reliabilities of DL(n, 1, n − 2), known as the daisy chain in the literature. © 1997 John Wiley & Sons, Inc. Networks 30: 81–90, 1997

Recently, J. Gordon and S. Srikanthan (1990) gave a new approach to route a rearrangeable three-stage Clos network. However, their algorithm was suspected to be incomplete by Y.K. Chiu and W.C. Siu (1991), and by H.Y. Lee and J.D. Carpinelli (1994). We show that a modification of their algorithm assures a correct routing.

Metzner (1991) discussed a parallel algorithm to identify two disagreeing pages when comparing two replicated file copies. We show that this algorithm can also identify three disagreeing pages, if one additional comparison is allowed to resolve some possible ambiguity. We also discuss the relation between the file-copy problem and the group testing problem which has been widely studied.

A file in a distributed database system is replicated on M sites and may contain corrupted pages. Abdel-Ghafiar and El Abbadi gave a detection scheme assuming that the number of corrupted pages f

We give a new decomposition algorithm to route a rearrangeable three-stage Clos network in O(nr/sup 2/) time, which is faster than all existing decomposition algorithms. By performing a row-wise matrix decomposition, this algorithm routes all possible permutations, thus overcoming the limitation on realizable permutations exhibited by many other routing algorithms. This algorithm is extended to the fault tolerant Clos network which has extra switches in each stage, where it provides fault tolerance under faulty conditions and reduces routing time under submaximal fault conditions.

The author comments on recent papers studying the reliability of consecutively-connected systems. Subjects covered include: multi-state systems; linear/circular systems; and algorithms. The authors of one of the original papers discussed also reply to these comments.

Three of the most well known double-loop networks are the distributed double-loop computer network (DDLCN), the daisy chain, and the braided ring. We compute the exact reliabilities of all three networks. We also extend the results on double-loop networks to directed chordal rings.

Abstract We propose a new routing strategy for the KYKLOS II multiprocessor interconnection network that achieves minimum distance for the path between any two processors. For KYKLOS II with 2n processors, the average distance is shorter than those of previous routing strategies by approximately 2 log2n. The traffic density, a measure of traffic concentration, is better than previous strategies for up to 2000 processors, though asymptotically inferior to a strategy proposed by Jenevein and Menezes. © 1994 by John Wiley & Sons, Inc.

Recently, W. Najjar and J.L. Gaudilot (1990) have proposed a new measure for network reliability which they called network resilience. One attractive feature of network resilience is that it has a good and simple approximation, as purported to have been proved by the authors (also supported by simulations). We show that their proof has several pitfalls remained to be fixed.>

Abstract Double loop networks have been intensively studied as interconnecting networks. However, the reliability analysis of such networks has hit a snag since the usual measure of reliability, the graph connectivity, is completely powerless as all double loops, if connected, are 2‐connected. Recently, Hwang and Li introduced a new analysis by partitioning cutsets into isolated and nonisolated ones and gave results on both types. Along the same line, we extent their results to the survival reliability model by showing that when each node fails independently with a very small probability, G(1, 1 + [n/2]) is the most reliable connected double loop network except when n = 3 and 9, in which case G(1, 2) is the most reliable. © 1993 by John Wiley & Sons, Inc.

Abstract A two‐stage rearrangeable broadcast network (called an ordinary network here) that has been studied recently has a partial concentrator on the input side. We extend this study to a network with two partial concentrators: one on the input side and the other on the output side. We first study the network as a connection network and derive conditions for its rearrangeability. We show that the conditions are tight in some cases. We then show that a particular construction that meets the rearrangeability conditions actually yields a broadcast network. © 1993 John Wiley & Sons, Inc.

In a $( t,n,m )$-multipartitioning problem, t lists of $nm$ ordered numbers are partitioned into n sets, where each set contains m numbers from each list. The goal is to maximize some objective function that depends on the sum of the elements in each set and is called the partition function. The authors use the recently developed theory of majorization and Schur convexity with respect to partially ordered sets to study optimal multipartitions for the above problem. In particular, they apply the results to construct a class of counterexamples to a recent conjecture of Du and Hwang, which asserts that (classic) Schur convex functions can be characterized as the partition functions for $( 1,n,m )$-multipartitioning problems having monotone optimal solutions.

Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used in the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over an algorithm given by D.Z. Du et al. (1991), for which the competitive ratio was 2.75. It also proves a conjecture made by them. A new application of group testing techniques for high-speed networks is discussed.>

Abstract A chordal ring is a degree‐3 regular graph with n vertices on a ring and n/2 chords determined by a parameter h. Chordal rings are attractive as topologies for computer networks due to their simple structures and short diameters. In this work, we study the reliabilities of chordal rings assuming each edge can independently fail with probability p. For p small, the usual criterion to measure the reliability of a network is its line‐connectivity. We show that all chordal rings have the same line‐connectivity and the same super line‐connectivity. We analyze the reliabilities of chordal rings by using the recently developed notions of isolated and nonisolated cutsets and list the optimal choices of h for n ≤ 30.

Abstract We give a survey up to 1989 on the Steiner tree problems which include the four important cases of euclidean, rectilinear, graphic, phylogenetic and some of their generalizations. We also provide a rather comprehensive and up‐to‐date bibliography which covers more than three hundred items.

Consider a set P of points in a normed space whose unit sphere is a d-dimensional symmetric polytope with 2d extreme points. This paper proves that there always exists a Steiner minimum tree whose Steiner points are located only at points whose coordinates appear in points of P. This generalizes a recent result of Snyder on d-dimensional rectilinear space, which itself extends Hanan’s well-known and much quoted result on the rectilinear plane. Furthermore, the proof in this paper is much simpler than Snyder’s proof, even considerably shorter than Hanan’s proof. A consequence of this result is that the Steiner problem for P in such a space is reduced to a Steiner problem on graphs and is solvable by any existing Steiner graph algorithms. The paper also conjectures that such a reduction is impossible if the polytope has more than $2d$ extreme points and provides partial support for the conjecture.

Partial concentrators have been shown to be useful in the construction of various types of interconnecting networks. It is shown how a large class of combinatorial designs, which are well studied in the literature, can be used to construct partial concentrators and thus provide a direct link between the fields of combinatorial designs and switching networks. A construction efficiency factor called the cost ratio is introduced, and some lower bounds on the capacity of partial concentrators having certain characteristics are established. It is shown how to use various combinatorial designs to construct partial concentrators having these same characteristics and corresponding capacities.>

A family of finitely many continuous functions on a polytope X, namely (g/sub i/(x))/sub i in I/, is considered, and the problem of minimizing the function f(x)=max/sub i in I/g/sub i/(x) on X is treated. It is shown that if every g/sub i/(x) is a concave function, then the minimum value of f(x) is achieved at finitely many special points in X. As an application, a long-standing problem about Steiner minimum trees and minimum spanning trees is solved. In particular, if P is a set of n points on the Euclidean plane and L/sub s/(P) and L/sub m/(P) denote the lengths of a Steiner minimum tree and a minimum spanning tree on P, respectively, it is proved that, for any P, L/sub S/(P)>or= square root 3L/sub m/(P)/2, as conjectured by E.N. Gilbert and H.O. Pollak (1968).>

Consider a system with n components and a reliability function $R(x_1 , \cdots ,x_n )$ where $x_j $ is the reliability of component j. Suppose that each component consists of the same set of parts, say $h_i $ parts of type i for $i = 1, \cdots ,m$, which must all work for the component to work. The problem is to assign $nh_i $ parts of type $i,i = 1, \cdots ,m$, with various part reliabilities to the n components to maximize the system reliability. An assignment is called monotone if all the best parts go to one component, all the next best parts go to the second component, and so on. The optimality of monotone assignments for systems with symmetric and asymmetric reliability functions is studied. In particular, it is proved that monotone assignments are optimal for s-stage k-out-of-n systems.

The classical binomial group testing problem studies plans to sort defectives from good items using a minimum number of group tests where a group test is a test applicable to any subset of items with a yes and no answer to the question of whether the subset contains any defectives. In a multinomial group testing problem, each item can be in one of k ordered states and a group test on a subset always reveals the highest state of any item in the subset. Two properties known for binomial group testing are the cutoff point, which characterizes when individual testing is optimal, and the monotonicity, which states that the minimum expected number of tests increases in the probability of an item being defective. This paper studies the multinomial group testing problem and gives a new sufficient condition that guarantees individual testing is optimal. (A sufficient condition in Kumar [SIAM J. Appl. Math., 19 (1970), pp. 340–350] is shown to be incorrect.) It is also shown that the monotonicity does not hold for the multinomial case.

The binomial group-testing problem consists of finding by group tests all defectives in a given set of items, each of which independently has probability p of being defective. The conjecture that the expected number of tests under an optimal testing algorithm is nondecreasing in p has recently been proved by transplanting the probability structure of the set of defective items. It is proved that this approach works in a much broader setting in which the states of items are dependent and the tests have k possible outputs. The results apply to the collision-resolution problem in random-multiple-access-channel communication.>

Abstract We show that the digraphs proposed independently by Imase and Itoh, and Reddy, Pradhan and Kuhl to minimize diameters essentially retain all the nice properties of de Bruijn digraphs and yet are applicable to any number of nodes. In particular we give results on the number of loops, the link connectivities and connectivities, the embedding properties and the self‐routing properties for these digraphs.

Recently the problems of detecting two defectives under various testing models have been studied as a forum for exploring the boundaries between easy problems and hard problems in combinatorial searching. In this paper five levels of optimality to measure the difficulty are defined. These five levels are minimax, almost surely minimax, measure p minimax, first-order minimax, and order-of-magnitude minimax. A new procedure is given, which is almost surely minimax for the parity check model, improving the previously best procedure which is measure p minimax.

The group testing problem is to find by group tests all defectives in a given set of items each of which independently has probability p of being defective. The group testing problem originated with the famous Dorfman’s blood testing problem and has since found many industrial applications including a recent one on multiple-access communication. Unfortunately, optimal group testing algorithms are not known in general. In particular, a very plausible conjecture that the expected number of tests should be nondecreasing in p for $0\leqq p < 1$ has remained open since 1981. In this paper we prove this conjecture by an innovative approach.

Various switching network construction advantageously use modules known as partial concentrators. A partial concentrator is an n-input, m-output, single-stage switching device in which each input has access to some but not all of the outputs. A partial concentrator is said to have capacity c, if, for any kor=2. In addition, it is shown that the rate of decrease of the cost ratio with increasing n is logarithmic for M=2, and polynomial for M>or=3.>

We comment on the paper by Raghavendra, Gerla, and Avizienis recently published in this TRANSACTIONS [3]. We point out a different routing strategy leading to a skip distance with diameter roughly √3N as compared to the diameter 2√N from the "optimal" skip distance obtained in that paper.

A communication network with multiple users sharing a common broadcast channel is considered. Ak-channel is defined to be a channel that can carry up tok-1successful transmissions simultaneously, but simultaneous transmissions bykor more users cause a collision and no successful transmissions take place. The question arises as to how to organize transmissions to avoid collisions or to resolve them efficiently when they occur. The most conservative approach is to use a roll call scheme, which guarantees that collisions never occur. However, other approaches may sometimes be more efficient. It is supposed that each user has the same probabilitypof wanting to transmit, and for several different models the conditions onpunder which roll call is the most efficient scheme for ak-channel are determined.

A class of plausible inequalities between conditional probabilities is considered involving random subsets of a set which arise, for example, in studying the capacity of a multiple access channel. Some of the inequalities are true and can be proved by the Fortuin-Kasteleyn-Ginibre (FKG) inequality. Some others are true but seem to need other methods. Still others are false. The results also apply to studying the conditional probability of the failure of a device designed to achieve reliability by using redundant parts, given side information about the failure of some of its components.

Abstract Recently Trietsch and Handler extended a conjecture of Pollak and Gilbert on the Steiner ratio to a model first studied by Gilbert where the cost of an edge is flow dependent. For three given points Trietsch and Handler showed that the maximum Steiner ratio is achieved when the cost is independent of the flow, i. e., the extended conjecture is reduced to the original conjecture. They also conjectured that the two conjectures are equivalent for any number of given points. In this paper we give a counterexample to their conjecture if the number of given points is at least four. We also replace their proof for the three‐point case, which depends heavily on computer‐aided calculations, by a simple geometric proof.

In the paper, four theorems describing conditions under which a three-stage multiconnection network is nonblocking for different routing strategies are formulated and proved. These theorems hold for any values of the structural parameters of a network. For some networks having a small number of outer stage switches, these theorems give significantly lower numbers of required middle stage switches than theorems currently known.

Abstract A consecutive‐2 system is a graph where each vertex can either work or fail and the system fails if and only if two vertices incident to the same edge both fail. The simplest probability structure attached to such systems is to assume that vertex i has probability p i of failing and the states of the vertices are stochastically independent. For a given graph G of n vertices and a given set P of n probabilities, an optimal consecutive‐2 system is the triple ( G,P,M ), where M is a mapping from P to the vertices of G such that the probability of the system failing is minimum. Consecutive‐2 systems have been widely studied when the graph is either a line or a cycle. In this paper we study optimal consecutive‐2 systems which consist of many lines or many cycles. Our results provide optimal mappings that depend only on the rankings of the individual failure probabilities and not on their actual values. Moreover, we show by examples that rankings alone are probably insufficient to solve cases more complex than those solved in this paper.

Abstract A well known engineering principle in introducing redundancy to a system is that component‐level redundancy is better than system‐level redundancy. However, the mathematical demonstration of this principle is usually for coherent systems constructed by one sequential synthesis and one parallel synthesis (the proof consists of showing that the parallel synthesis should be at the component level). In this article we demonstrate the same principle for systems constructed by parallel‐sequential‐parallel synthesis, one parallel synthesis at the component level and one at the system level. We show that the parallel synthesis at the component level should have more redundancy. The particular vehicle we use for this demonstration is the comparison of blocking probabilities for a 2‐port network known as channel graphs. The crux of the mathematical demonstration is the lemma that [1 − Π (1 − P )]1/a decreases in a, 0 ≤ pi ≤ 1, i = 1,…, n.

We consider networks of processors where each processor either has one in-link and one out-link, or two in-links and two out-links. We study three properties of such networks: 1) diameter, 2) connectivity, and 3) the ring property. We propose a class of networks which seem to achieve the optimum as far as these three properties are concerned.

Recently interest in rearrangeable Clos networks has risen again, due to their potential uses in data networks and computing systems. Much research has been directed towards the construction of efficient control algorithms. However, the literature has seemed not to be aware of an important link between the control algorithms and the edge coloring algorithms for bipartite graphs. In this paper we show that a recent edge coloring algorithm of Gabow can be used to obtain a control algorithm faster than any existing one.

The problem of computing the blocking probabilities for spiderweb channel graphs is known to be difficult even under the simplifying Lee model. There have been only a few successful cases reported in the literature, all restricted to special types of four-stage channel graphs. In this paper we give an efficient method which computes the exact blocking probabilities (under the Lee model) for a large class of spiderweb channel graphs which are not restricted to four stages.

Suppose we are given two disjoint linearly-ordered subsets $A_m $ and $B_n $ of a linearly-ordered set S. The problem is to determine the linear ordering of their union (i.e., to “merge” $A_m $ and $B_n $) by means of a sequence of pairwise comparisons between an element of $A_m $ and an element of $B_n $. An algorithm to merge $A_m $ and $B_n $ is called M-optimal if it minimizes the maximum number of comparisons required where the maximum is taken over all possible ordering of $A_m \cup B_n $. Let $f_m (k)$ denote the largest n such that $A_m $ and $B_n $, can be merged in k comparisons by an M-optimal algorithm. The determination of $f_3 (k)$ has been an open problem for a long time. In this paper we give a constructive proof that\[ f_3 (1) = 0,\quad f_3 (2) = 1,\quad f_3 (3) = 1,\quad f_3 (4) = 2, \]\[ f_3 (5) = 3,\quad f_3 (6) = 4,\quad f_3 (7) = 6,\quad f_3 (8) = 8, \]and for $r \geqq 3$,\[ f_3 (3r) = \left[ {\frac{{43}}{7}2^{r - 2} } \right] - 2, \]\[ f_3 (3r + 1) = \left[ {\frac{{107}}{7}2^{r - 3} } \right] - 2, \]\[ f_3 (3r + 2) = \left[ {\frac{{17 \cdot 2^r - 6}}{7}} \right] - 1, \]where $[x]$ denotes the integral part of x.

The blocking probabilities for spiderweb channel graphs are well known to be difficult to compute. Recently, Takagi studied a class of spiderweb channel graphs and gave recursive equations for computing their blocking probabilities. In this paper we use a recent result in combinatorics to give a dosed form solution for the recursive equations. Consequently, the blocking probability for any graph in this class can be expressed in a form involving at most two nested summations.

Let P be a set of pomts m the plane with rectdmear distance An O(n log n) algonthm for the construeUon ofa Voronot diagram for P ts gwen By using prewously known results, a mmmaal spammuag tree for P can be derived from a Voronot diagram for P m hnear tmae.

Abstract Suppose P is a set of points in the plane with rectilinear distance. Let l s (P) denote the length of a Steiner minimal tree for P. Let l r (P) denote the semiperimeter of the smallest rectangle with vertical and horizontal lines which encloses P. It is well known that l s (P) ≥ l r (P) for ∣P∣ ≥ 3 where ∣P∣ denotes the cordinality of P. In designing placement algorithms for printed circuits, l r (P) has been used as an estimate of l s (P) when ∣P∣ is small. Therefore, it is of some interest to know the value of In this paper we show ρ n tends to (√n+1)/2 and we give the exact value of ρ n for n ≤ 10.

Abstract A balanced switching network is a multistage switching network where all channel graphs G(α, β) (the union of all paths from the input switch α to the output switch β) are isomorphic. In this paper we: (1) derive some necessary conditions for the existence of balanced switching networks realizing various types of channel graphs, (2) solve completely the problem of the construction of 3‐stage balanced switching networks, and (3) give a recursive procedure to construct a class of balanced switching networks with more than three stages.

Abstract We study a class of five‐stage connecting networks which are generalizations of the AMDF networks recently proposed. The terminals of a network in this class are partitioned into various zones while two terminals of the same zone have a larger number of distinct paths connecting them than two terminals of different zones. Furthermore, to facilitate the analysis of blocking probabilities, we require that the linear graphs (union of all connecting paths) for all intrazone pairs of terminals be isomorphic and fixed, and the linear graphs for all interzone pairs be isomorphic. We show that balanced incomplete block designs can be used to construct large classes of such networks. For a fixed number of distinct paths, we also determine the symmetric linear graph which has the smallest blocking probability, and show that the network which yields this linear graph (for interzone pairs) can always be constructed if a certain balanced incomplete block design exists.

Channel graphs have long been recognized as a useful tool in studying the blocking probabilities of switching networks. A channel graph is said to be superior to another channel graph if the blocking probability of the former never exceeds that of the latter assuming common but arbitrary link occupancies for the two graphs. Proving superiority has become a standard way to compare channel graphs in the literature. It turns out that many such comparisons can be abstracted as optimal partition problems. In an optimal partition problem, we have a setS, and a cost functionC(P)defined on a partitionPofS. The problem is to find the partition which minimizesC(P). In this paper we study some optimal partition problems whenC(P)assumes some special forms. We also show that our result has direct applications to the comparison of channel graphs with respect to superiority.

Abstract A minimal rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees have potential application to wire layout for printed circuits. Unfortunately, at present no practical algorithm is known for constructing these trees in general. We present two algorithms, each requiring a number of operations proportional to only a low degree polynomial in the number of points to be interconnected, for the special cases in which all the points of A lie on a small number of parallel lines or on the boundary of a rectangle.

Abstract We begin with a three‐stage linear graph in which the first stage has a single node u and the third stage a single node v. The second stage has k independent nodes, each of which is connected by one link to u and to v. In general, we can form a (2n+1)‐stage linear graph recursively by letting each node in the second stage of a three‐stage linear graph be replaced by a copy of a (2n‐1)‐stage linear graph. A link can either be in the busy state or the idle state. We assume that the states of each link are mutually independent and that any link between stage i and stage i + 1 has the probability I.z of being idle. The nodes u and v are said to be connectable if there exists at least one path from u to v with no busy link. Let P(u, v) denote the probability of such a path existing. Further, let N(2n+1, k) denote the set of (2n+1)‐stage linear graphs whose center stages have k nodes. In this paper, we determine the size of N(2n+1, k). We also give the linear graph in N(2n+1, k) which has the largest P(u, v) and the one which has the smallest. We then show how our results apply to a recent problem in connecting networks.

We consider an abstract partitioning problem which has applications to the design of standard libraries of multipurpose units (such as multi-purpose circuit cards) and to storage allocation in the presence of users with conflicting demands. Although the general problem of finding minimum cost partitions appears to be very difficult, we describe a dynamic programming approach which can be quite efficient if the parameters for the items to be partitioned take on only a limited number of distinct values.

Suppose we are given two disjoint linearly ordered subsets A and B of a linearly ordered set C , say A = { a 1 < a 2 < ··· < a m } and B = { b 1 < b 2 < ··· < b n }. The problem is to determine the linear ordering of their union (i.e. to merge A and B ) by means of a sequence of pairwise comparisons between an element of A and an element of B (which we refer to in the paper as the ( m, n ) problem). Given any algorithm s to solve the ( m, n ) problem, we are interested in the maximum number of comparisons K s ( m, n ) required under all possible orderings of A ∪ B . An algorithm s is said to be minimax if K s ( m, n ) = K ( m, n ) where K ( m, n ) = mins K s ( m, n ) It is a rather difficult task to determine K ( m, n ) in general. In this study the authors are only concerned with the minimax over a particular class of merging algorithms. This class includes the tape merge algorithm, the simple binary algorithm, and the generalized binary algorithm.

In this paper we present a new algorithm for merging two linearly ordered sets which requires substantially fewer comparisons than the commonly used tape merge or binary insertion algorithms. Bounds on the difference between the number of comparisons required by this algorithm and the information theory lower bounds are derived. Results from a computer implementation of the new algorithm are given and compared with a similar implementation of the tape merge algorithm.