bluuebunny/crossref_metadata_2025_split huggingface dataset:
Additive graph spanners
Authors: Liestman Arthur L. , Shermer Thomas C. 
Published: May 2007

AbstractA 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

AbstractIn 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

AbstractWe 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

AbstractThis 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

AbstractA 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

AbstractIn 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

AbstractWe 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

AbstractIn 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

AbstractBroadcast 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

AbstractA 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

AbstractIn 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

AbstractGiven 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

AbstractWe 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

AbstractThe 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

AbstractThis 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

AbstractLet 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

AbstractIn 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

AbstractThis 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

AbstractWe 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

AbstractMotivated 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

AbstractThis 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

AbstractThis 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.
Optimal communication in networks with randomly distributed byzantine faults
Authors: Blough Douglas M. , Pelc Andrzej 
Published: May 2007

AbstractWe consider the problem of efficient information exchange in a communication network whose nodes and/or links are subject to Byzantine faults that are randomly and independently distributed through the network. The goal is almost safe communication, i.e., getting to every fault‐free node information about every other fault‐free node, with probability converging to one as the number of nodes grows. We present nonadaptive almost‐safe communication schemes working for various networks in asymptotically optimal time and using an asymptotically optimal number of message bits.