bluuebunny/crossref_metadata_2025 huggingface dataset:
A pseudopolynomial network flow formulation for exact knapsack separation
Authors: Andrew Boyd E.
Published: May 2007

The NP‐complete separation problem for the knapsack polyhedron 𝓅 is formulated as a side‐constrained network flow problem with a pseudopolynomial number of vertices and edges. It is demonstrated that the primal polyhedron associated with this formulation can be projected onto an appropriate subspace to yield 𝓅 and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of 𝓅. Practical consequences of the formulation are discussed.
On a tree‐shaped facility location problem of Minieka
Authors: Rabinovitch Ramon , Tamir Arie
Published: May 2007

Minieka and Hakimi et al. considered the problem of locating a tree‐shaped facility of a given length in a tree network, with the objective of maximizing the sum of node distances from this facility. They stated the complexity of the model as an open problem. We prove that it is NP‐complete and provide a pseudopolynomial time algorithm.
Parallel contractions of grids for task assignment to processor networks
Authors: Ben‐Natan Ron , Barak Amnon
Published: May 2007

LetGbe a simple connected undirected graph. A contraction φ ofGis a mapping fromG=G(V, E)toG'=G'(V', E'), whereG'is also a simple connected undirected graph, such that ifu, vφV(G)are connected by an edge (adjacent) inG, then either φ(u)= φ(v) orφ(u)and φ(v)are adjacent inG'. Consider a family of contractions, called bounded contractions, in which ∀v'∈V', the degree ofv'inG', DegG'(v'), satisfiesDegG'(v')≤ |φ−1(v')|, where φ−1(v')denotes the set of vertices inGmapped tov'under φ. These types of contractions are useful in the assignment (mapping) of parallel programs to a network of interconnected processors, where the number of communication channels of each processor is small. In this paper, we are concerned with bounded contractions of two‐dimensional grids such as mesh, hexagonal, and triangular arrays. For each of these graphs, we give contraction schemes that yield mappings of the minimal possible degree, such that the topology of the resulting graphs is identical to that of the desired target graph. We also prove that some contractions are not possible, regardless of their degree.
Shortest path problems with node failures
Authors: Jaillet Patrick
Published: May 2007

Consider the problem of finding the shortest paths from a node source s to a node sink t in a complete network. On any given instance of the problem, only a subset of the intermediate nodes can be used to go from s to t, the subset being chosen according to a given probability law. We wish to find an a priori path from s to t such that, on any given instance of the problem, the sequence of nodes defining the path is preserved but only the permissible nodes are traversed, the others being skipped. The problem of finding an a priori path of minimum expected length is defined as the Probabilistic Shortest Path Problem (PSPP). Note that if the network is not originally complete, the PSPP methodology can still be used if we first add each missing edge, together with a deterministic length (being defined by an alternative path using nodes that have no probability of failure). In this paper, after discussing potential applications of the PSPP, we study the complexity of this class of problems. We first show that the problem is, in general, NP‐hard and then we develop polynomial time procedures for special cases of it. We also consider the complexity of a related problem: the Probabilistic Minimum Spanning Tree Problem (PMSTP). Finally, we provide a discussion of the implications of the results.
Series‐parallel subgraphs of planar graphs
Authors: Elmallah Ehab S. , Colbourn Charles J.
Published: May 2007

In this paper, we show that every 3‐connected (3‐edge‐connected) planar graph contains a 2‐connected (respectively, 2‐edge‐connected) spanning partial 2‐tree (series‐parallel) graph. In contrast, a recent result implies that not all 3‐connected graphs contain 2‐edge‐connected series‐parallel spanning subgraphs.
Networks communicating for each pairing of terminals
Authors: Csaba László , Faudree Ralph J. , Gyárfás András , Lehel Jenö , Schelp Richard H.
Published: May 2007

Let G be a multigraph of maximum degree Δ and with a set of t vertices of degree one, called terminals. We call G a (Δ, t)‐network if for any pairing of its terminals there exist edge‐disjoint paths in G between those pairs (t is even). The concept of (Δ, t)‐networks is introduced to model the situation when switching processors having Δ ports are to be connected in such a way that simultaneous communication is possible for any pairing of the free ports. We establish some properties of (Δ, t)‐networks. In particular, we investigate optimal (or near‐optimal) networks and obtain lower and upper bounds on the function n(Δ, t), the minimum number of interior nodes a (Δ, t)‐network can have.
A message‐routing strategy for multicomputer systems
Authors: Choi Hyeong‐Ah , Esfahanian Abdol‐Hossein
Published: May 2007

A natural communication problem in a multicomputer system, such as the hypercube, is that a processor (called the source) wants to send a message to a number of other processors (destinations). A message‐routing paradigm for such a multidestination communication has been formulated as finding a subgraph called an Optimal Communication Tree (OCT). We prove that the problem of finding an OCT is NP‐hard for the n‐cube graph as well as for a graph whose maximum degree is at most three. Heuristics for finding suboptimal communication trees for the hypercube multicomputer are discussed.
Counting k‐component forests of a graph
Authors: Myrvold Wendy
Published: May 2007

We describe an algorithm for computing the number of k‐component spanning forests of a graph G that runs in polynomial time for fixed k. The algorithm is based on earlier work by Liu and Chow. Our contributions are a simpler graph‐theoretic proof of their formula and a demonstration of how Jacobi's Theorem can be applied to improve the asymptotic time complexity. By matroid duality, the number of connected spanning subgraphs of cyclomatic number c of a planar graph equals the number of c + 1‐component forests in the dual. Thus, one application of this research is an algorithm for counting connected spanning unicyclic subgraphs of a planar graph. We show this can be done in time O(M(n)), where M(n) is the time complexity of multiplying together two n by n matrices.
Network transformations and bounding network reliability
Authors: Brown Jason I. , Colbourn Charles J. , Devitt John S.
Published: May 2007

Three transformations on networks that reduce the all‐terminal network reliability (probability of connectedness) of a network are shown not to increase any coefficient in one form of the reliability polynomial of the network. These transformations yield efficiently computable lower bounds on each coefficient of the reliability polynomial. A further transformation due to Lomonosov is shown not to decrease any coefficient in the reliability polynomial, leading to an efficiently computable upper bound on each coefficient. The resulting bounds on coefficients can, in turn, be used to obtain a substantial improvement on the Ball—Provan strategy for computing lower and upper bounds on the all‐terminal reliability. © 1993 John Wiley & Sons, Inc.
A catalog of steiner tree formulations
Authors: Goemans Michel X. , Myung Young‐Soo
Published: May 2007

We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem. © 1993 by John Wiley & Sons, Inc.
Canceling most helpful total cuts for minimum cost network flow
Authors: Ervolina Thomas R. , McCormick S. Thomas
Published: May 2007

We present a polynomial algorithm for the minimum cost network flow problem (MCNF). It is a dual algorithm that is based on canceling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on canceling most helpful total cuts, which are cuts together with augmentation amounts that lead to the maximum possible increase in the dual objective function. We show how to compute a most helpful total cut and give a rigorous dual conformal decomposition theorem. Canceling most helpful cuts is, in spirit, dual to an algorithm of Weintraub as modified by Barahona and Tardos. We also show how our algorithm specializes to the case of shortest s–t path with nonnegative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight. © 1993 by John Wiley & Sons, Inc.
The traveling salesman problem with cumulative costs
Authors: Bianco Lucio , Mingozzi Aristide , Ricciardelli Salvatore
Published: May 2007

In this paper, we consider a special case of the time‐dependent traveling salesman problem where the objective is to minimize the sum of all distances traveled from the origin to all other cities. Two exact algorithms, incorporating lower bounds provided by a Lagrangean relaxation of the problem, are presented. We also investigate a heuristic procedure derived from dynamic programming that is able to evaluate the distance from optimality of the produced solution. Computational results for a number of problems ranging from 15 to 60 cities are given. They show that problems up to 35 cities can be solved exactly and problems up to 60 cities can be solved within 3% from optimality. © 1993 by John Wiley & Sons, Inc.
Graph endpoint coloring and distributed processing
Authors: De Werra D. , Hell P. , Kameda T. , Katoh N. , Solot Ph. , Yamashita M.
Published: May 2007

A graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. © 1993 by John Wiley & Sons, Inc.
Sharp bounds on the order, size, and stability number of graphs
Authors: Hansen Pierre , Zheng Maolin
Published: May 2007

We consider graphs G = (V,E) with order ρ = |V|, size e = |E|, and stability number β0. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © 1993 by John Wiley & Sons, Inc.
Grid spanners
Authors: Liestman Arthur L. , Shermer Thomas C.
Published: May 2007

A t‐spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at most t edges in the subnetwork. We present t‐spanners with small maximum or average degree for multidimensional grids. We show how to construct small maximum degree 3‐spanners for d‐dimensional grids for d © 2 and constant average degree 3‐spanners for d‐dimensional grids. We also present t‐spanners of minimum average degree for 2‐dimensional grids. © 1993 by John Wiley & Sons, Inc.
A polynomial time solvable concave network flow problem
Authors: Guisewite G. M. , Pardalos P. M.
Published: May 2007

We prove that the single‐source uncapacitated (SSU) version of the concave cost network flow problem, when all arcs except one have linear cost, is in the class P of problems solvable in time polynomial in the problem input length. This contrasts the corresponding result without network constraints, in which the problem is known to be NP‐hard [6]. © 1993 by John Wiley & Sons, Inc.
On the star—delta transformation in network reliability
Authors: Traldi Lorenzo
Published: May 2007

Lehman observed that star—delta and delta—star transformation cannot always be applied to networks with perfect (unfailing) vertices so as to exactly preserve reliability, and Rosenthal and Frisque introduced imperfect vertices to make exact delta—star transformations possible. We give an explicit condition that is satisfied if and only if a network with perfect vertices can be subjected to an exact star—delta or delta—star transformation, and we discuss the introduction of imperfect faces to make exact star—delta transformations possible. © 1993 by John Wiley & Sons, Inc.
Decomposition of bipartite graphs under degree constraints
Authors: Broersma H. J. , Faudree R. J. , Van Heuvel J. Den , Veldman H. J.
Published: May 2007

Let G = (A, B; E) be a bipartite graph. Let e1, e2 be nonnegative integers, and f1, f2 nonnegative integer‐valued functions on V(G) such that ei ≦ |E| ≦ e1 + e2 and fi(v) ≦ d(v) ≦ f1(v) + f2(v) for all v ϵ V(G) (i = 1, 2). Necessary and sufficient conditions are obtained for G to admit a decomposition in spanning subgraphs G1 = (A, B; E1) and G2 = (A, B; E2) such that |Ei| ≦ ei and dGi(v) ≦ fi(v) for all v ϵ V(G) (i = 1, 2). The result generalizes a known characterization of bipartite graphs with a k‐factor. Its proof uses flow theory and is a refinement of the proof of an analogous result due to Folkman and Fulkerson. By applying corresponding flow algorithms, the described decomposition can be found in polynomial time if it exists. As an application, an assignment problem is solved. © 1993 by John Wiley & Sons, Inc.
Bounds for the general capacitated routing problem
Authors: Jansen Klaus
Published: May 2007

This paper presents heuristics that are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP). For the VRP, heuristics that consist of an optimum partitioning of a TSP tour generated by Christofides are known and have a worst‐case error of 7/2 − 3/q for even q, where q is the capacity of the vehicles. If we apply a partitioning to an optimum TSP tour, the worst‐case error becomes 3 − 2/q for even q. We generalize these results to the GCRP and give also some lower bounds. © 1993 John Wiley & Sons, Inc.
Shortest paths in stochastic networks with ARC lengths having discrete distributions
Authors: Corea Gehan A. , Kulkarni Vidyadhar G.
Published: May 2007

In this work, we compute the distribution of L*, the length of a shortest (s, t) path, in a directed network G with a source node s and a sink node t and whose arc lengths are independent, nonnegative, integer valued random variables having finite support. We construct a discrete time Markov chain with a single absorbing state and associate costs with each transition such that the total cost incurred by this chain until absorption has the same distribution as does L*. We show that the transition probability matrix of this chain has an upper triangular structure and exploit this property to develop numerically stable algorithms for computing the distribution of L* and its moments. All the algorithms are recursive in nature and are illustrated by several examples. © 1993 by John Wiley & Sons, Inc.
On uniformly optimally reliable graphs for pair‐connected reliability with vertex failures
Authors: Amin A. T. , Siegrist K. T. , Slater P. J.
Published: May 2007

Let G be a probabilistic (n,m) graph in which each vertex exists independently with fixed probability p, 0 < p < 1. Pair‐connected reliability of G, denoted PCv(G;p), is the expected number of connected pairs of vertices in G. An (n,m) graph G is uniformly optimally reliable if PCv(G;p) ≧ PCv(H;p) for all p, 0 < p < 1, over all (n,m) graphs H. It is shown that there does not exist a uniformly optimally reliable (n,m) graph whenever n ≦ m < ∼2n2/9. However, such graphs do exist for some other values of m. In particular, it is established that every complete k‐partite pseudoregular graph on n vertices, 2 ≦ k < n, is uniformly optimally reliable. © 1993 by John Wiley & Sons, Inc.
Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs
Authors: Coullard Collette R. , Rais Abdur , Rardin Ronald L. , Wagner Donald K.
Published: May 2007

The 2‐connected Steiner subgraph problem is that of finding a minimum‐weight 2‐connected subgraph that spans a subset of distinguished vertices. This paper presents linear‐time algorithms for solving the 2‐connected Steiner subgraph problem on two special classes of graphs, W4‐free graphs and Halin graphs. Although different in detail, the algorithms adopt a common strategy exploiting known decompositions. As a special case, the algorithms also solve the Traveling Salesman Problem on W4‐free graphs and Halin graphs. © 1993 by John Wiley & Sons, Inc.
An upper bound on the number of cliques in a graph
Authors: Farber Martin , Hujter Mihály , Tuza Zsolt
Published: May 2007

Giving a partial solution to a conjecture of Balas and Yu [Networks 19 (1989) 247–235], we prove that if the complement of a graph G on n vertices contains no set of t + 1 pairwise disjoint edges as an induced subgraph, then G has fewer than (n/2t)2t maximal complete subgraphs. © 1993 by John Wiley & Sons, Inc.
Uniform d‐emulations of rings, with an application to distributed virtual ring construction
Authors: Bakker Erwin M. , van Leeuwen Jan
Published: May 2007

Emulations are a special kind of structure‐preserving mappings between processor interconnection networks (graphs). In this paper, the notion of emulation is generalized to the notion of d‐emulation for any d ≧ 1. Several problems concerning the complexity of (uniform) d‐emulations are studied. It is shown that the problem of deciding for arbitrary graphs H and G whether H can be uniformly d‐emulated on G is NP‐complete for every fixed d ϵ N. Also, it is shown that the problem of deciding for arbitrary rings R and planar graphs G whether R can be uniformly 2‐emulated on G is NP‐complete. Further, a constructive proof is given of the fact that there always exists a uniform 3‐emulation of a ring R on a graph G = (V, E) if |VRy| = k. |VG| and k ϵ N. This uniform 3‐emulation of R on G is used as the basis for the Distributed Virtual Ring Construction Algorithm that only uses 2|E| messages of O(1) bits and has time complexity ≦ 2(|V| − 1). A traversal of the constructed virtual ring costs 2(|V| − 1) messages. © 1993 John Wiley & Sons, Inc.
On the edge forwarding index problem for small graphs
Authors: Bouabdallah Abdelmadjid , Sotteau Dominique
Published: May 2007

For a given graph G of order n, a routing R is a set of n(n − 1) elementary paths specified for every ordered pair of vertices in G. The edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.
Undirected loop networks
Authors: Chen Sheng , Jia Xing‐De
Published: May 2007

Let M, d, and k be positive integers. We say that M is feasible with respect to d and k if there exists a set A = {0, ± 1, ±a2 …, ±ak} such that the Cayley graph associated with Z/(M) and A has diameter less than or equal to d. Such a Cayley graph is a model for undirected loop communication networks. Denote M(d, k) the maximal feasible number M with respect to d and k. In the paper, an explicit formula for M(d, 2) is obtained. Also, when k ≧ 3, a lower bound for M(d, k) is established. © 1993 by John Wiley & Sons, Inc.
μ‐star: An indirect star network
Authors: Chen Wen‐Shyen E. , Lee Kyungsook Y. , Liu Ming T.
Published: May 2007

The star graph has a smaller degree and diameter than the well‐known n‐cube, and can be an alternative to the n‐cube for systems with a large number of nodes [2]. In our previous work [11], three different indirect star‐type networks were obtained from the star graph: the indirect star network I, the indirect star network II, and the star‐delta network. However, the indirect star networks I & II are constructed from large switches, and do not perform as well as the indirect cube‐type networks of comparable switch sizes. Also, they are not modular. The star‐delta network is modular, but it employs varying switch sizes for different switching stages, and has a lower performance than the indirect cube‐type networks based on comparable switch sizes. Moreover, the switch sizes for all three indirect star networks grow with the network size.

In this work, a new indirect star network, called the μ‐star network, is proposed. Being modular and constructed from (2 × 2) crossbar switches, the new network is an improvement over previously proposed indirect star‐type networks. The μ‐star network is analyzed for its performance and the analytic results are verified through simulations. © 1993 by John Wiley & Sons, Inc.
Fault—tolerant hypercube broadcasting via information dispersal
Authors: Gargano L. , Rescigno A. A. , Vaccaro U.
Published: May 2007

Broadcasting is the process of disseminating a message originated at one node of a network to all other nodes. In this paper, we consider the problem of broadcasting reliably in the hypercube in presence of either transmission or link failures. We propose broadcasting protocols under various assumptions on the communication model. Our broadcasting protocols make use of Rabin's Information Dispersal Algorithm. © 1993 by John Wiley & Sons, Inc.
The minimum order of a cayley graph with given degree and diameter
Authors: Hamidoune Yahya Ould
Published: May 2007

In a previous paper, we proved the following: The order of a vertex‐transitive directed graph with outdegree r and diameter ρ is at least 2 + 2r + (ρ − 3)(1 + [r/2]). In the case of a Cayley graph, where r ≥ 3 and ρ ≥ 5, we show here that the minimal order is (ρ + 1)(1 + [r/2]). This bound improves the above one. In the Abelian case with ρ ≥ 6, we show that equality holds if and only if the graph is either the lexicographic product of a directed cycle with a complete graph or obtained from this last graph by deleting one 1‐factor with a special structure. © 1993 by John Wiley & Sons, Inc.
Renormalization of two—terminal reliability
Authors: Harms Daryl D. , Colbourn Charles J.
Published: May 2007

An exact algebraic method for computing the two‐terminal reliabilities in a network is approximated to yield an effective upper bound that can be computed in time that is polynomial in the size of the network. The result yields both a strong aprioribound and a strong a posteriori technique for improving upper bounds from other upper‐bounding methods. ©1993 by John Wiley & Sons, Inc.
A unidirectional ring partition problem
Authors: Hu Jyun‐Jy , Yang Shi‐Nine , Chern Maw‐Sheng
Published: May 2007

Let R = (V, E) be a unidirectional ring network where V corresponds to the set of nodes and E corresponds to the set of directed communication links. A partition of R divides R into several disjoint chains. For each partition P, there is associated a communication cost C(P). The optimal ring partition problem is to find a partition P* of R such that C(P*) = minpC(P). In this paper, we first formulate the ring partition problem into a recurrence relation. By solving the recurrence relation, we show that the ring partition can be accomplished distributively in one pass, i.e., the message complexity of our distributed ring partition algorithm is O(|V|), which is optimal. © 1993 by John Wiley & Sons, Inc.
The most vital edges of matching in a bipartite graph
Authors: Hung Chun‐Nan , Hsu Lih‐Hsing , Sung Ting‐Yi
Published: May 2007

Let G = (V,E) be an undirected graph having an edge weight we ≥ 0 for each e ϵ E. An edge is called a most vital edge (with respect to weighted matching) if its removal from G results in the largest decrease in the total weight of the maximum weighted matching. In this paper, we study the most vital edges of matching in a weighted bipartite graph. We present an O(n3) algorithm to obtain the most vital edges. © 1993 by John Wiley & Sons, Inc.
A new class of interconnection networks based on the alternating group
Authors: Jwo Jung‐Sing , Lakshmivarahan S. , Dhall S. K.
Published: May 2007

This paper introduces a new class of interconnection scheme based on the Cayley graph of the alternating group. It is shown that this class of graphs are edge symmetric and 2‐transitive. We then describe an algorithm for (a) packet routing based on the shortest path analysis, (b) finding a Hamiltonian cycle, (c) ranking and unranking along the chosen Hamiltonian cycle, (d) unit expansion and dilation three embedding of a class of two‐dimensional grids, (e) unit dilation embedding of a variety of cycles, and (f) algorithm for broadcasting messages. The paper concludes with a short analysis of contention resulting from a typical communication scheme. Although this class of graphs does not possess many of the symmetry properties of the binary hypercube, with respect to the one source broadcasting, these graphs perform better than does a hypercube, and with respect to the contention problem, these graphs perform better than do the star graphs and are close to the hypercube. © 1993 by John Wiley & Sons, Inc.
Optimization of the reliability polynomial in presence of mediocre elements
Authors: Katona G. O. H. , Woyczyński W. A.
Published: May 2007

Some connections between extremal set theory and the optimization of the reliability polynomial are shown. Then the concept of the reliability polynomial is generalized for the case when the elements can have three different states: good, mediocre and bad. The state of the device can be described by a 0,1,2 sequence. Such a state is called operative if the device operates when its elements are in the states described by the sequence. The maximum of the generalized reliability polynomial is studied under the condition that the set of operative states froms an antichain. © 1993 by John Wiley & Sons, Inc.
Additive graph spanners
Authors: Liestman Arthur L. , Shermer Thomas C.
Published: May 2007

A spanning subgraph S = (V, E′) of a connected simple graph G = (V, E) is a f(x)‐spanner if for any pair of nodes u and v, dS(u, v) ≦ f(dG(u, v)), where dG and dS are the usual distance functions in graphs G and S, respectively. We are primarily interested in (t + x)‐spanners, which we refer to as additive spanners. We construct low‐degree additive spanners for X‐trees, pyramids, and multidimensional grids. We prove, for arbitrary t > 0, that to determine whether a given graph G has an additive spanner with no more than m edges is NP‐complete. © 1993 by John Wiley & Sons, Inc.
Fast fault‐tolerant parallel communication for de bruijn and digit‐exchange networks using information dispersal
Authors: Lyuu Yuh‐Dauh
Published: May 2007

In this paper, the space‐efficient Information Dispersal Algorithm (IDA) is applied to fault‐tolerant parallel communication in the de Bruijn andd‐way digit‐exchange networks, which is a generalized butterfly (Omega) network. LetN=dndenote the size of the de Bruijn network. Our routing scheme runs in 2n+ 1 time using constant size buffers (if the routing information is not counted). Ford= [nInn], it probability of successful routing is at least 1 −N−InN/2. The scheme also toleratesO(N)random link failures with probability at least 1 −N(7−InInn)/6. We also propose a routing scheme for the d‐way digit‐exchange network such that similar bounds hold. Both schemes run within the said time bounds without queuing delay. ©1993 by John Wiley & Sons, Inc.
Routing permutations on a graph
Authors: Ramras Mark
Published: May 2007

We study off‐line routing of permutations π in arbitrary connected graphs. By insisting that routings be congestion‐free, we can rephrase the problem as one of factoring π into a minimal length product of permutations that move messages a distance of at most one, or alternatively, as the problem of finding a shortest path from the identity permutation to π in a certain Cayley graph of the symmetric group on the nodes. For the complete k‐partite graph Kn,n,….,n, every π can be routed in two steps. We investigate a method for finding minimal factorizations. It involves finding perfect matchings in certain bipartite graphs associated with π. For the n‐dimensional hypercube Qn, the well‐known upper bound of 2n − 1 for the number of steps in which all π′s can be routed (obtained via the Beneš network) is reduced to 2n − 2. We prove some results about permutations of Qn that are close to the antipodal map. A number of examples on Q3 and Q4 illustrate our method and compare it with those used by others. © 1993 by John Wiley & Sons, Inc.
Construction of large‐size interconnection networks with high performance
Authors: Shen Hong , Back Ralph‐Johan
Published: May 2007

This paper proposes a new method, recursive expansion (RE), for systematically constructing interconnection networks of arbitrary large size with high performance. On the basis of two small‐size networks, a frame and a unit, the RE method works in a manner of recursively replacing each node in the frame with an expanded network containing a set of copies of the unit and each edge in the frame with a set of interunit connections connecting a pair of the networks until a network of the desired size has been obtained. By RE, we can construct various kinds of large‐size and low‐cost interconnection networks. Two applications of the method, the ℋ︁Σr network based on the torus and the ℋ︁Σr network based on the hypercube, show that our method can produce networks with cost O((log3/2 n)/(log3/2 log n)) (degree O(1)) and O(log n log log n) (degree O(log log n)). In addition to low cost, networks constructed by RE also possess other properties such as high constructability, good extendability, symmetric topology, and efficient message routing. This paper describes an algorithm, for automatically constructing arbitrary large size networks with high performance. For constructing a network of size nr through r phases RE on the basis of a frame of degree df and a unit of size nu and degree du, the algorithm has a time complexity O((max{(df/nu), (du/r)})rn2r). Finally, a routing algorithm for networks constructed by RE is presented. The routing algorithm can realize point‐to‐point message routing without using a global routing table at each node and has a time complexity O((ku + kf)dfr), where ku and kf are diameters of the frame and of the unit, df is the degree of the frame, and r is the number of phases of RE to construct the network. © 1993 by John Wiley & Sons, Inc.
Reliability evaluation and decision problems in extra stage shuffle‐exchange MINs
Authors: Trahan Jerry L. , Rai Suresh
Published: May 2007

A multistage interconnection network (MIN) uses switching elements for interconnecting processors to memory or processors. This paper first considers a stochastic model of a shuffle exchange network (of sizeN) with an extra stage and develops terminal, broadcast, andK‐terminal reliability evaluation algorithms that run in timeO(log logN),O(logN), andO(klogN), respectively, wherek= |K|. Second, a deterministic model for the MIN is considered and decision problems in which one is interested in evaluating whether a network can effect a specified set of connections with a given set of failures are solved. We develop a set of approaches for the SENE for the terminal decision, broadcast decision, and network decision problems and for the generalS, Tdecision problem for an input setSand output setT. Each algorithm runs within time polynomial in the size of the SENE and the number of faults and, in some cases, logarithmic in the size of the SENE and polynomial in the number of faults. These approaches are based on either testing for the existence of an appropriate pathset or testing for the nonexistence of an appropriate cutset. ©1993 by John Wiley & Sons, Inc.
Asymmetrical multiconnection three‐stage clos networks
Authors: Varma Anujan , Chalasani Suresh
Published: May 2007

In this paper, we study routing problems in a general class of asymmetrical three‐stage Clos networks. This class covers many asymmetrical three‐stage networks considered by earlier researchers. We derive necessary and sufficient conditions under which this class of networks is rearrangeable with respect to a set ofmulticonnections, i.e., connections between subsets of input and output terminals. We first model the routing problem in these networks as a network‐flow problem. If the number of switching elements in the first and last stages of the network isO(f)and the number of switching elements in the middle stage ism, then the network‐flow model yields a routing algorithm with running timeO(mf3). We then show that the problem of routing a set of multiconnections in an asymmetrical Clos network can be transformed into the well‐studied problem of routing a set of pairwise connections in a more symmetric form of the network. This approach results in a routing algorithm with complexityO(mK2), whereKis the aggregate capacity of the interstage links in the network. ©1993 by John Wiley & Sons, Inc.
Maintaining bipartite matchings in the presence of failures
Authors: Sha Edwin Hsing‐Mean , Steiglitz Kenneth
Published: May 2007

We present an on‐line distributed reconfiguration algorithm for finding a new maximum matching incrementally after some nodes have failed. Our algorithm is deadlock‐free and, withkfailures, maintains at leastM–kmatching pairs during the reconfiguration process, whereMis the size of the original maximum matching. The algorithm tolerates failures that occur during reconfiguration. The worst‐case reconfiguration time isO(kmin(|A|, |B|)) afterkfailures, whereAandBare the node sets, but simulations show that the average‐case reconfiguration time is much better. The algorithm is also simple enough to be implemented in hardware. ©1993 by John Wiley & Sons, Inc.
Applications of E‐graphs in network design
Authors: Haynes Teresa W. , Lawson Linda M.
Published: May 2007

In this paper, we introduce a construction that produces graphs, calledE‐graphs, by replacing the edges in a core graph with a copy of a given graph. These graphs are generalizations of several graphs that have recently been presented as models for network designs, including theG‐network and its extensions. We discuss several invariant properties of these graphs with emphasis on those of interest in network design, such as number of edges, diameter, and domination number. ©1993 by John Wiley & Sons, Inc.
A new method for constructing minimal broadcast networks
Authors: Ventura Jose A. , Weng Xiaohua
Published: May 2007

Broadcast is the task of transmitting a message from any node in a network to all other nodes in the network. A minimal broadcast network (mbn) is a communication network in which a message can be broadcasted in minimum time regardless of the originator. In this article, a new method to construct such mbn's is presented. The new method improves the best known upper bounds on the minimum number of edges in mbn's for most cases. © 1993 by John Wiley & Sons, Inc.
A Bayesian analysis of simulation algorithms for inference in belief networks
Authors: Dagum Paul , Horvitz Eric
Published: May 2007

A belief network is a graphical representation of the underlying probabilistic relationships in a complex system. Belief networks have been employed as a representation of uncertain relationships in computer‐based diagnostic systems. These diagnostic systems provide assistance by assigning likelihoods to alternative explanatory hypotheses in response to a set of findings or observations. Approximation algorithms have been used to compute likelihoods of hypotheses in large networks. We analyze the performance of leading Monte Carlo approximation algorithms for computing posterior probabilities in belief networks. The analysis differs from earlier attempts to characterize the behavior of simulation algorithms in our explicit use of Bayesian statistics: We update a probability distribution over target probabilities of interest with information from randomized trials. For real ϵ, δ < 1 and for a probabilistic inference Pr[x|e], the output of an inference approximation algorithm in an (ϵ, δ)‐estimate of Pr[x|e] if with probability at least 1 – δ the output is within relative error ϵ of Pr[x|e]. We construct a stopping rule for the number of simulations required by logic sampling, randomized approximation schemes, and likelihood weighting to provide (ϵ, δ)‐estimates of Pr[x|e]. With Probability 1 – δ, the stopping rule is optimal in the sense that the algorithm performs the minimum number of required simulations. We prove that our stopping rules are insensitive to the prior probability distribution on Pr[x|e]. © 1993 by John Wiley & Sons, Inc.
Optimal multifacility defensive location on planes with rectilinear distances
Authors: Trietsch Dan
Published: May 2007

In this paper, we are concerned with the problem of optimally covering a large region with rectilinear distances by many service facilities. We assume that the number of customers is proportional to the area that they occupy and that each customer patronizes the nearest facility. Our objective is to locate the facilities in such a manner that the maximal area any future competitor facility can capture will be minimized. For Euclidean distances, it has been conjectured that the best arrangement is a triangular grid, yielding hexagonal service areas (honeycomb). In this paper, we show that an analogous arrangement is optimal for rectilinear distances. Furthermore, as in the Euclidean case, it minimizes both the average and the maximal distance for all customers to their nearest facilities. The service areas under the optimal solution are rectilinear circles—which are shaped as Euclidean squares tilted at 45° to the X‐ and Y‐axes. © 1993 by John Wiley & Sons, Inc.
A branch and bound algorithm for the capacitated minimum spanning tree problem
Authors: Malik Kavindra , Yu Gang
Published: May 2007

Given an undirected graph G = (N, E) with a cost associated with each edge C: E → R+ and a demand associated with each node A: N → R+. A special node is designated as the center. The capacitated minimum spanning tree (CMST) problem is to find a minimum spanning tree for graph G such that the sum of demands on each branch stem from the center does not exceed a given capacity. The CMST problem has many applications in network design, centralized telecommunications, and vehicle routing. In this paper, we present a new formulation and a full optimization algorithm by branch and bound. The lower bounds are generated by Lagrangean relaxation with tightening constraints. Computational results based upon the methodology presented are shown. © 1993 by John Wiley & Sons, Inc.
Finding all minimum‐size separating vertex sets in a graph
Authors: Kanevsky Arkady
Published: May 2007

We present a new algorithm based upon network flows for finding all minimum‐size separating vertex sets in an undirected and unweighted graph. The sequential implementation of our algorithm runs in Θ(Mn + C) = O(2kn3) time, where M is the number of minimum‐size separating vertex sets of the graph; n, the number of the vertices in the graph; m, the number of the edges in the graph; k, the connectivity of the graph, and C = kn min(k(m + n), A), where A is the complexity of the best maximum flow algorithm for unit networks. The parallel implementation runs either in O(k log n) deterministic time or in O(log2 n) randomized time using Θ(;M2n2 + knNα) = O(4k(n6/k2)) processors on a PRAM, where Nα is the number of processors needed for parallel matrix multiplication in O(log n) time on PRAM. © 1993 by John Wiley & Sons, Inc.
On locating path‐ or tree‐shaped facilities on networks
Authors: Hakimi S. L. , Schmeichel E. F. , Labbé Martine
Published: May 2007

The study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (≥1) such facilities. We will consider “center”, “median”, “max eccentricity”, and “max distance sum” location type problems for p = 1 or p > 1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whether a facility is path‐shaped or tree‐shaped. These cases lead to 64 problems. We will determine the algorithmic complexity of virtually all these problems. We conclude with a result that may be viewed as a generalization of the p‐Median theorem. © 1993 by John Wiley & Sons, Inc.
A differential game model of Nash equilibrium on a congested traffic network
Authors: Wie Byung‐Wook
Published: May 2007

This paper considers the problem of the competition among a finite number of players who must transport the fixed volume of traffic on a simple network over a prescribed planning horizon. Each player attempts to minimize his total transportation cost by making simultaneous decisions of departure time, route, and flow rate over time. The problem is modeled as a N‐person nonzero‐sum differential game. Two solution concepts are applied: [1] the open‐loop Nash equilibrium solution and [2] the feedback Nash equilibrium solution. Optimality conditions are derived and given an economic interpretation as a dynamic game theoretic generalization of Wardrop's second principle. Future extensions of the model are also discussed. The model promises potential applications to Intelligent Vehicle Highway Systems (IVHS) and air traffic control systems. © 1993 by John Wiley & Sons, Inc.
Finding minimum cost to time ratio cycles with small integral transit times
Authors: Hartmann Mark , Orlin James B.
Published: May 2007

Let D = (V, E) be a digraph with n vertices and m arcs. For each e ∈ E there is an associated cost ce and a transit time te; ce can be arbitrary, but we require te to be a non‐negative integer. The cost to time ratio of a cycle C is Λ(C) = ∑e∈cce/∑e∈c. Let E' ⊆ E denote the set of arcs e with te > 0, let Tu = max{tuv: (u, v) ∈ E} for each vertex u, and let T = ∑u∈v Tu. We give a new algorithm for finding a cycle C with the minimum cost to time ratio Λ(C). The algorithm's O(T(m + n lo g n)) running time is dominated by O(T) shortest paths calculations on a digraph with non‐negative arc lengths. Further, we consider early termination of the algorithm and a faster O(Tm) algorithm in case E – E' is acyclic, i.e., in case each cycle has a strictly positive transit time, which gives an O(n2) algorithm for a class of cyclic staffing problems considered by Bartholdi et al. The algorithm can be seen to be an extension of the O(nm) algorithm of Karp for the case in which te = 1 for all e ∈ E, which is the problem of calculating a minimum mean cycle. Our algorithm can also be modified to solve the related parametric shortest paths problem in O(T(m + n log n)) time. © 1993 by John Wiley & Sons, Inc.
Determining efficient facility locations on a tree network operating as a FIFO M/G/1 queue
Authors: Prasad Srinivas Y. , Batta Rajan
Published: May 2007

In this article, we study the problem of locating a server on a tree network that operates as a FIFO M/G/1 queue. The goal is to identify sets of efficient facility locations with respect to moments of the response time. The results are illustrated via an example. © 1993 by John Wiley & Sons, Inc.
Backordering in a multiperiod transshipment network
Authors: Sandbothe Richard A.
Published: May 2007

This paper demonstrates that when the backordering of demand is permitted in a Multiperiod Transshipment Problem it is necessary to include additional side constraints that restrict the number of backorders a node can have in a time period. Computer experience on a small set of test problems is presented to validate this problem formulation. Two stricter backorder constraint sets are also presented, both of which are piecewise linear. For these piecewise linear constraint cases, a method is outlined whereby the original network problem is transformed into a mixed integer linear network flow problem that is very difficult to solve. Some highlights of work by other authors in solving mixed integer linear network flow problems are given. © 1993 by John Wiley & Sons, Inc.
A two‐commodity flow formulation for the traveling salesman and the makespan problems with time windows
Authors: Langevin André , Desrochers Martin , Desrosiers Jacques , Gélinas Sylvie , Soumis Fraňlois
Published: May 2007

We present a new two‐commodity flow formulation for the traveling salesman problem. Each commodity corresponds to a resource that is either distributed or picked up along the tour of all nodes. This formulation is partcularly well suited to handling time window constraints; the resource used is then the time. This formulation can be extended to the makespan problem. For a n‐node problem, the linear relaxation of the formulation involves only O(n) constraints and O(n2) variables. Implementation issues are discussed and numerical experimentations have been realized for problems of up to 60 nodes. © 1993 by John Wiley & Sons, Inc.
Cycle prefix digraphs for symmetric interconnection networks
Authors: Faber Vance , Moore James W. , Chen William Y. C.
Published: May 2007

Motivated by the study of large graphs with given degree and diameter, and the recent interest in the design of highly symmetric interconnection networks (e.g., the study of Cayley digraphs), we are led to the search for large vertex symmetric digraphs with given degree and diameter. The main result of this paper is the construction of a new class of vertex symmetric directed graphs, Γδ(D) (δ ≥ D) that have degree δ, diameter D, and (δ + 1)δ … (δ – D + 2) vertices. The graphs Γδ(D) are first found in the notation of Cayley coset digraphs. Then, we discover that they have a very simple representation in terms of sequences like the commonly studied networks such as the hypercube, de Bruijn graphs, and Kautz graphs. Based on the sequence representation, we give a simple shortest‐path routing scheme. We also show that the average distance in our digraph Γδ(D) is very close to its diameter D. As a consequence, it follows that the natural routing scheme, which is even simpler than the shortest‐path routing, is nearly optimal on an average basis. © 1993 by John Wiley & Sons, Inc.
Parallel iterative search methods for vehicle routing problems
Authors: Taillard É.
Published: May 2007

This paper presents two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles. Indeed, using a simple implementation of taboo search as an iterative search method, every best‐known solution to classical problems was found. The first partition method (based on a partition into polar regions) is appropriate for Euclidean problems whose cities are regularly distributed around a central depot. The second partition method is suitable for any problem and is based on the arborescence built from the shortest paths from any city to the depot. Finally, solutions that are believed to be optimum are given for problems generated on a grid. © 1993 by John Wiley & Sons, Inc.
On stochastic spanning tree problem
Authors: Geetha S. , Nair K. P. K.
Published: May 2007

This paper considers a generalized version of the stochastic spanning tree problem in which edge costs are random variables and the objective is to find a spectrum of optimal spanning trees satisfying a certain chance constraint whose right‐hand side also is treated as a decision variable. A special case of this problem with fixed right‐hand side has been solved polynomially using a parameteric approach. Also, the same parametric method without increasing the complexity order has been extended to include the right‐hand side also as a decision variable. In this paper, two different methods are given for solving the generalized problem. First, a different parametric method better than the earlier one is given. Then, a method that makes use of the efficient extreme points of the convex hull of the mappings of all the spanning trees in a bicriteria spanning tree problem is presented. But it is shown that in the worst case the bicriteria method is superior. © 1993 by John Wiley & Sons, Inc.