The rapid expansion of cloud computing, especially machine learning, is leading to a significant increase in the global energy footprint of computing. Improvements in the energy efficiency of hardware and infrastructure are nearing the point of diminishing returns, and system developers will soon be compelled to drastically improve the energy efficiency of their software. For that, it is essential to have energy clarity: developers/operators must be able to accurately and productively understand how the energy usage of their hardware and software is influenced by workload, configuration, and other factors. We propose energy interfaces as a way to achieve that clarity: an energy interface provides concise, accurate, actionable information about the "energy behavior" of a system, much like a functional interface does for its semantic behavior. Preliminary experimentation suggests that obtaining and using such energy interfaces is feasible. We believe that some form of energy interfaces will one day become as central to system building as functional interfaces.

We consider the problem of partitioning the edge set of a graph $G$ into the minimum number $\tau(G)$ of edge-disjoint complete bipartite subgraphs. We show that for a random graph $G$ in $G(n,p)$, where $p$ is a constant no greater than $1/2$, asymptotically almost surely $\tau(G)$ is between $n- c(\log_{1/p} n)^{3+\epsilon}$ and $n - (2+o(1))\log_{1/(1-p)} n$ for any positive constants $c$ and $\epsilon$.

3-D packing is an NP-hard problem with wide applications in microelectronic circuit design such as 3-D packaging, 3-D VLSI placement and dynamically reconfigurable FGPA design. We present a complete representation for general non-slicing 3-D floorplan or packing structures, which uses a labeled tree and dual sequences. For each compact placement, there is a corresponding encoding. The number of possible tree-sequence combinations is (n+1)n-1(n!)2, the lowest among complete 3-D representations up to date. The construction of placement from an encoding needs O(n2) in the worst case, but in practical cases we expect O(n4⁄3 log n) time on average for circuit blocks with limited length/width ratios. Experimental results show promising performance using the labeled tree and dual sequences on 3-D floorplan and placement optimizations

A local graph partitioning algorithm finds a cut near a specified starting vertex, with a running time that depends largely on the size of the small side of the cut, rather than the size of the input graph. In this paper, we present a local partitioning algorithm using a variation of PageRank with a specified starting distribution. We derive a mixing result for PageRank vectors similar to that for random walks, and show that the ordering of the vertices produced by a PageRank vector reveals a cut with small conductance. In particular, we show that for any set C with conductance Phi and volume k, a PageRank vector with a certain starting distribution can be used to produce a set with conductance (O(radic(Phi log k)). We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most oslash, whose small side has volume at least 2bin time O(2 log m/(2blog2m/oslash2) where m is the number of edges in the graph. By combining small sets found by this local partitioning algorithm, we obtain a cut with conductance oslash and approximately optimal balance in time O(m log4m/oslash)

We consider the random graph model $G(\mathbf{w})$ for a given expected degree sequence ${\mathbf w} =(w_1, w_2, \ldots, w_n)$. If the expected average degree is strictly greater than 1, then almost surely the giant component in G of $G({\mathbf w})$ has volume (i.e., sum of weights of vertices in the giant component) equal to $\lambda_0 {\rm Vol}(G) + O(\sqrt{n}\log^{3.5} n)$, where $\lambda_0$ is the unique nonzero root of the equation \[ \sum_{i=1}^n w_i e^{-w_i\lambda} = (1-\lambda) \sum_{i=1}^n w_i, \] and where ${\rm Vol}(G)=\sum_i w_i.$

In a WDM optical network, each fiber link can carry a certain set of wavelengths /spl Lambda/= {/spl lambda//sub 1/,/spl lambda//sub 2/,...,/spl lambda//sub W/}. One scheme for tolerating a single link failure (or node failure) in the network is the path protection scheme, which establishes an active path and a link-disjoint (or node-disjoint) backup path, so that in the event of a link failure (node failure) on the active path, data can be quickly re-routed through the backup path. We consider a dynamic scenario, where requests to establish active-backup paths between a specified source-destination node pair arrive sequentially. If a link-disjoint (node-disjoint) active-backup path pair is found at the time of the request, the paths are established; otherwise, the request is blocked. In this scenario, at the time a request arrives, not every fiber link will have all W wavelengths available for new call establishment, as some of the wavelengths may already have been allocated to earlier requests and communication through these paths may still be in progress. We assume that the network nodes do not have any wavelength converters. This paper studies the existence of a pair of link-disjoint (node-disjoint) active-backup paths satisfying the wavelength continuity constraint between a specified source-destination node pair. First we prove that both the link-disjoint and node-disjoint versions of the problem are NP-complete. Then we focus on the link-disjoint version and present an approximation algorithm and an exact algorithm for the problem. Finally, through our experimental evaluations, we demonstrate that our approximation algorithm produces near-optimal solutions in almost all of the instances of the problem in a fraction of the time required by the exact algorithm.

A crucial problem that needs to be solved is the allocation of memory to processors in a pipeline. Ideally, the processor memories should be totally separate (i.e., one port memories) in order to minimize contention; however, this minimizes memory sharing. Idealized sharing occurs by using a single shared memory for all processors but this maximizes contention. Instead, in this paper we show that perfect memory sharing of shared memory can be achieved with a collection of *two*-port memories, as long as the number of processors is less than the number of memories. We show that the problem of allocation is NP-complete in general, but has a fast approximation algorithm that comes within a factor of 3/2. The proof utilizes a new bin packing model, which is interesting in its own right. Further, for important special cases that arise in practice the approximation algorithm is indeed optimal. We also describe an incremental memory allocation algorithm that provides good memory utilization while allowing fast updates.

Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation. However, due to the computational demands of these approaches, applications to large problems such as spatiotemporal data and high resolution imagery have been slow to appear. The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning making it feasible to apply them to very large grouping problems. Our approach is based on a technique for the numerical solution of eigenfunction problems known as the Nyström method. This method allows one to extrapolate the complete grouping solution using only a small number of samples. In doing so, we leverage the fact that there are far fewer coherent groups in a scene than pixels.

Many massive graphs (such as the WWW graph and Call graphs) share certain universal characteristics which can be described by the so-called "power law." In this paper, we, examine three important aspects of power law graphs, (1) the evolution of power law graphs, (2) the asymmetry of in-degrees and out-degrees, (3) the "scale invariance" of power law graphs. In particular, we give three increasingly general directed graph models and one general undirected graph model for generating power law graphs by adding at most one node and possibly one or more edges at a time. We show that for any given edge density and desired power laws for in-degrees and out-degrees, not necessarily the same, the resulting graph will almost surely have the desired edge density and the power laws for the in-degrees and out-degrees. Our most general directed and undirected models include nearly all known power law evolution models as special cases. Finally, we show that our evolution models generate "scale invariant" graphs. We describe a method for scaling the time in our evolution model such that the power law of the degree sequences remains invariant.

We study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add "shortcut" edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRN's) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the "cutwidth" of an express ring translating into the "tree depth" of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-(2d-1) multiring. 3) Every depth-d multiring /spl Mscr/ can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of /spl Mscr/ resides at a corner of the mesh. 4) Every depth-d HRN /spl Hscr/ can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of /spl Hscr/ resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRN's that are asymptotically tight for large N and d.

We propose a random graph model which is a special case of sparse random graphs with given degree sequences. This model involves only a small number of parameters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. Furthermore, from these parameters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We will illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We will also discuss the threshold function, the giant component, and the evolution of random graphs in this model. 1 Introduction Is the World Wide Web completely connected? If not, how big is the largest component, the second largest component, etc.? Anyone who has "surfed" the Web for any length of time will come away ...

No abstract available.

We study the parallel scheduling problem for a new modality of parallel computing: having one workstation "steal cycles" from another. We focus on a draconian mode of cycle-stealing, in which the owner of workstation B allows workstation A to take control of B's processor whenever it is idle, with the promise of relinquishing control immediately upon demand. The typically high communication overhead for supplying workstation B with work and receiving its results militates in favor of supplying B with large amounts of work at a time; the risk of losing work in progress when the owner of B reclaims the workstation militates in favor of supplying B with a sequence of small packets of work. The challenge is to balance these two pressures in a way that maximizes the amount of work accomplished. We formulate two models of cycle-stealing. The first attempts to maximize the expected work accomplished during a single episode, when one knows the probability distribution of the return of B's owner. The second attempts to match the productivity of an omniscient cycle-stealer, when one knows how much work that stealer can accomplish. We derive optimal scheduling strategies for sample scenarios within each of these models.

Have1 and Liebl [1973], and Leighton 119841.' The networks of interest are defined in section 1.3.' For any graph 53, we denote by (%I the number of nodes in %.

We study a combinatorial problem that is motivated by “client–server” schedulers for parallel computations. Such schedulers are often used, for instance, when computations are being done by a cooperating network of workstations. Our results expose and quantify a control–memory trade-off for such schedulers, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-toward-leaves or leaves-toward-root. The combinatorial problem for the root-toward-leaves case takes the following form. (The leaves-toward-root case gives rise to a dual formulation, which yields the same trade-offs.) Consider, for integersk,N> 0, an algorithm that employskFIFO queues in order to schedule anN-leaf binary tree in such a way that each nonleaf node of the tree is executed before its children. We establish a trade-off between the number of queues used by the algorithm—which we view as measuring thecontrol complexityof the algorithm—and thememory requirementsof the algorithm, as embodied in the required capacity of the largest-capacity queue. Specifically, for each integerk∈ {1, 2, ..., log2N}, letQk(N) denote the minimax per-queue capacity for ak-queue algorithm that schedules allN-leaf binary trees; letQ*k(N) denote the analogous quantity forcompletebinary trees. We establish the following bounds: For generalN-leaf binary trees, for allk, [formula]≤Qk(N) ≤ 2N1/k+ 1. For complete binary trees, we derive tighter bounds. We prove that for all constantk, Q*k(N) = Θ[formula]. For generalk, we obtain the following bounds: [formula]≤Q*k(N) ≤ (4k)1−1/k[formula]. Similar trade-offs are readily established for trees of any fixed branching factor.

A salvage-embedding (S-embedding) maps an M-leaf complete binary tree into $\mathcal{G}$ an ($N > M$)-leaf complete binary tree $\mathcal{H}$, the fraction G of whose leaves have been labeled GOOD. The S-embedding maps leaves of $\mathcal{G}$ one-to-one to GOOD leaves of $\mathcal{H}$; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio $H\mathop = \limits^{def} M/GN$, and its congestion, the largest number of edges $\mathcal{G}$ that get “routed” across the same edge of $\mathcal{H}$. We study three scenarios. In the worst-case scenario, given any target harvest $H \leq \frac{1}{2}$, one can S-embed a $2^{\lfloor {\log ( HGN )} \rfloor }$-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $\log \log N + $ a constant depending only on G and H, no matter how the GOOD leaves are distributed; this congestion cannot be lowered by more than a small constant factor. In the expected-case scenario—where leaves of $\mathcal{H}$ are labeled GOOD or not, independently, with fixed probability—with probability exceeding $1 - N^{ - \Omega ( 1 )} $, for any target harvest $H \leq 1/8$, one can S-embed a $2^{\lfloor {HN} \rfloor } $-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $O( \log \log \log N )$. In the salvaging scenario, we present an algorithm that, in time $O( CN ( \log N )^{3C + 2} )$, S-embeds in a given a leaf-labeled $\mathcal{H}$ the largest possible $\mathcal{G}$, subject to the prespecified bound C on congestion. This work is inspired by the problem of salvaging a fault-free subnetwork of a leaf-tree machine—a tree architecture whose leaves hold “full-power” processors and whose nonleaf nodes hold “rudimentary” processors that route messages and perform simple combining tasks.

We study a combinatorial problem that is motivated by '(client-server" schedulers for networks of

The authors discuss the general state of affairs in a variety of related areas ranging from software safety, reliability, and testing, protocol specification and verification, network congestion-control and reliability, to communication security and complexity. They intend to identify useful theory and tools, point out connections between different areas, and to a large extent, raise a number of questions whose answers may still lie far beyond the limits of current knowledge. Some of these areas are still in a very primitive state and call for new ideas, bold approaches, radical thinking, and perhaps extraordinary efforts. The paper was originally the overview section of a Bellcore technical report. The remainder of the report consisted of the following surveys in selected areas: A. Quality, reliability, and safety by Sid Dalal, Bob Horgan and Jon Kettenring (1994). B. Congestion control and network reliability by Brian Coan and Dan Heyman (1994). C. Protocol specification and validation by Linda Ness. D. Security and correctness of computation by Stuart Haber.>

A class of routing problems on connected graphs G is considered. Initially, each vertex v of G is occupied by a “pebble” that has a unique destination $\pi ( v )$ in G (so that $\pi $ is a permutation of the vertices of G). It is required that all the pebbles be routed to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected, and the pebbles at each edge’s endpoints are interchanged. The problem of interest is to minimize the number of steps required for any possible permutation $\pi $. This paper investigates this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs, and Cayley graphs. In addition, this routing problem is related to certain network flow problems, and to several graph invariants including diameter, eigenvalues, and expansion coefficients.

The authors give a new upper bound for the diameter $D( G )$ of a graph G in terms of the eigenvalues of the Laplacian of G. The bound is \[ D ( G ) \leq \left\lfloor \frac{\text{cosh}^{ - 1} ( n - 1 )}{\text{cosh}^{ - 1} ( \frac{\lambda _n + \lambda _2 }{\lambda _n - \lambda _2 } )} \right\rfloor + 1, \] where $0 \leq \lambda _2 \leq \cdots \leq \lambda _n $ are the eigenvalues of the Laplacian of G and where $\lfloor {} \rfloor $ is the floor function.

It is proved that every strongly connected directed graph with n nodes and at least $\lfloor ( n + 1 )^2 /4 \rfloor $ edges must contain an even cycle. This is best possible, and the structure of extremal graphs is discussed.

We consider a class of routing problems on connected graphs G. Initially, each vertex v of G is occupied by a "pebble" which has a unique destination T(V) in G, so that m is a permutation of the vertices of G.It is required to route all the pebbles to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected and the pebbles at each edge's endpoints are interchanged.The problem of interest is to minimize the number of steps required for any possible permutation m.The odd-even sorting network shows that in the very special case that G is an n-vertex path, any permutation can be routed in n steps.Here we investigate this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs and various Cayley graphs.In addition, we relate this routing problem to certain network flow problems, and to several graph invariants including diameter, eigenvalues and expansion coefficients.Three of our results are the following: (i) Any permutation can be routed on any n-vertex connected graph in less than 3n steps.

The multiparty communication complexity concerns the least number of bits that must be exchanged among a number of players to collaboratively compute a Boolean function $f ( x_1 , \ldots ,x_k )$, while each player knows at most t inputs for some fixed $t < k$. The relation of the multiparty communication complexity to various hypergraph properties is investigated. Many of these properties are satisfied by random hypergraphs and can be classified by the framework of quasi randomness. Namely, many disparate properties of hypergraphs are shown to be mutually equivalent, and, furthermore, various equivalence classes form a natural hierarchy. In this paper, it is proved that the multiparty communication complexity problems are equivalent to certain hypergraph properties and thereby establish the connections among a large number of combinatorial and computational aspects of hypergraphs or Boolean functions.

The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded-degree graph with an $O(1)$-separator can be embedded in a hypercube of the same size with dilation and congestion both $O(1)$. It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.

How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and $O(n\log n)$ edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size $n^\alpha $ has $O(n)$ edges if $\alpha < \frac{1}{2}$; $O(n\log n)$ edges if $\alpha = \frac{1}{2}$; $O(n^{2\alpha } )$ edges if $\alpha > \frac{1}{2}$.

This paper considers the following game on a hypercube, first suggested by Lagarias and Saks. Suppose $2^n$ pebbles are distributed onto vertices of an n-cube (with $2^n$ vertices). A pebbling step is to remove two pebbles from some vertex and then place one pebble at an adjacent vertex. The question of interest is to determine if it is possible to get one pebble to a specified vertex by repeatedly using the pebbling steps from any starting distribution of $2^n$ pebbles. This question is answered affirmatively by proving several stronger and more general results.

An optical orthogonal code (OOC) is a family of

Article Free Access Share on Optimal simulations by Butterfly Networks Authors: Sandeep Bhatt Department of Computer Science, Yale University, New Haven, CT Department of Computer Science, Yale University, New Haven, CTView Profile , Fan Chung Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJ Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJView Profile , Jia-Wei Hong Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NY Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NYView Profile , Arnold Rosenberg Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 192–204https://doi.org/10.1145/62212.62229Published:01 January 1988Publication History 24citation283DownloadsMetricsTotal Citations24Total Downloads283Last 12 Months20Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

How small can the diameter be made by adding a matching to an n-cycle? In this paper this question is answered by showing that the graph consisting of an n-cycle and a random matching has diameter about $\log _2 n$, which is very close to the best possible value. It is also shown that by adding a random matching to graphs with certain expanding properties such as expanders or Ramanujan graphs, the resulting graphs have near optimum diameters.

The fractional covering number$\tau^*$ of a hypergraph $H = ( V, E )$ is defined to be the minimum possible value of $\sum_{x \in V} t( x )$ where t ranges over all functions $t : V \to \mathbb{R}$ which satisfy $\sum_{x \in e} t ( x ) \geqq 1$ for all edges $e \in E$. In the case of ordinary graphs G, it is known that $2\tau^* ( G )$ is always an integer. By contrast, it is shown (among other things) that for any rational $p/q\geqq 1$, there is a 3-uniform hypergraph H with $\tau^* ( H ) = p/q$.

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.

Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead. In this paper we investigate simulations of tree machines; the fact that divide-and-conquer algorithms are programmed naturally on trees motivates our investigation. Among various proposals for parallel computing the boolean hypercube has emerged as a particularly versatile network. It is well known that programs for multidimensional grid machines, for example, can be executed on a hypercube with no communications overhead by embedding the grid as a subgraph of the hypercube. Our first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. We also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks. It is natural to ask if any sparse network can simulate every binary tree efficiently. Somewhat surprisingly, we construct a universal bounded-degree network on N nodes for which every N node binary tree is a spanning tree. In other words, every binary tree can be simulated on our universal network with no overhead. This improves previous bounds on the sizes of universal graphs for trees.

In this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. We prove that the average time required for the move-to-front heuristic is no more than p/2 times that of the optimal order and this bound is best possible. Hilbert's inequalities will be used to derive large classes of inequalities some of which can be applied to obtain tight worst-case bounds for several self-organizing heuristics.

Abstract We study the problem of orienting all the undirected edges of a mixed multigraph so as to preserve reachability. Extending work by Robbins and by Boesch and Tindell, we develop a linear‐time algorithm to test whether there is an orientation that preserves strong connectivity and to construct such an orientation whenever possible. This algorithm makes no attempt to minimize distances in the resulting directed graph, and indeed the maximum distance, for example, can blow up by a factor proportional to the number of vertices in the graph. Extending work by Chvátal and Thomassen, we then prove that, if a mixed multigraph of radius r has any strongly connected orientation, it must have an orientation of radius at most 42 + Ar. The proof gives a polynomial‐time algorithm for constructing such an orientation.

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.

We consider the problem of determining the multistage network with the fewest crosspoints for given sizes of input and output terminal sets, traffic load, number of stages and blocking probability. In this paper, we present a solution for this problem when the sizes of the input and output terminal sets are greater than a certain value.

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.