bluuebunny/crossref_metadata_2025_split huggingface dataset:
Shortest paths, single origin‐destination network design, and associated polyhedra
Authors: Magnanti Thomas L. , Mirchandani Prakash 
Published: May 2007

AbstractWe study a specialized version of network design problems that arise in telecommunications, transportation, and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single‐facility loading problem and certain “common break‐even point” versions of the two‐facility and three‐facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the two‐facility loading problem are strongly NP‐hard, but that a shortest path solution provides an asymptotically “good” heuristic; and (iii) characterize the optimal solution (i.e., specify a linear programming formulation with integer solutions) of the common break‐even point versions of the two‐facility and three‐facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities. © 1993 by John Wiley & Sons, Inc.
Edge fault tolerance in graphs
Authors: Harary Frank , Hayes John P. 
Published: May 2007

AbstractA graph or multigraph G* is k‐edge fault‐tolerant with respect to a graph G, denoted k‐EFT(G), if every graph obtained by removing any k edges from G* contains G. We observe that for k sufficiently large a k‐EFT(G) graph must be a multigraph, and we present some basic conditions that such multigraphs must meet. We then study the problem of constructing k‐EFT(G) graphs that are optimal in that they contain the minimum number of edges among all k‐EFT(G) graphs. Families of optimal k‐EFT(G) graphs, where G is the n‐node path or cycle, are presented for all k and n. We also give an optimal 1‐EFT design for the n‐dimensional hypercube. © 1993 by John Wiley & Sons, Inc.
Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry
Authors: Akl S. G. , Qiu K. , Stojmenović I. 
Published: May 2007

AbstractThe star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, few parallel algorithms are known for these networks. In this paper, we present several data communication schemes and basic algorithms for these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the algorithms proposed here can be applied. Indeed, we believe that these algorithms are interesting and important in their own right and are fundamental to the design of solutions on the star and pancake networks to a host of other problems. © 1993 by John Wiley & Sons, Inc.
On the adjacency properties of paley graphs
Authors: Ananchuen W. , Caccetta L. 
Published: May 2007

AbstractIn the application of graph theory to problems arising in network design, the requirements of the network can be expressed in terms of restrictions on the values of certain graph parameters such as connectivity, edge‐connectivity, diameter, and independence number. In this paper, we focus on networks whose requirements translate into adjacency restrictions on the graph representing the network. More specifically, a graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. The problem that arises is that of characterizing graphs having property P(m,n,k). In this paper, we present properties of graphs satisfying the adjacency property. In particular, for q  1(mod 4), a prime power, the Paley graph Gq of order q is the graph whose vertices are elements of the finite field 𝔽q; two vertices are adjacent if and only if their difference is a quadratic residue. For any m, n, and k, we show that all sufficiently large Paley graphs satisfy P(m,n,k). © 1993 by John Wiley & Sons, Inc.
Some minimum gossip graphs
Authors: Labahn Roger 
Published: May 2007

AbstractWhat is the minimum number of edges that a graph on n vertices must have to allow gossiping by bidirectional telephone calls within ⌈log2 n⌉ rounds? Besides general estimates, this question is finally answered for integers of the form n = 2p − 2 (p ≥ 3) or n = 2p − 4 (p ≥ 6), and for n = 10, 12. Moreover, for n = 14, we prove the uniqueness of such a graph. © 1993 by John Wiley & Sons, Inc.
Communication structures in fault‐tolerant distributed systems
Authors: Pradhan Dhiraj K. , Meyer Fred J. 
Published: May 2007

AbstractThe impact of communication structures on the robustness and performance of distributed computing systems is discussed. Communication structures are categorized as (1) point‐to‐point, (2) bus, and (3) multistage switching. The most significant networks that have been proposed are discussed. Networks are compared with respect to (1) connectivity, (2) diameter, (3) average distance, (4) diameter in the presence of faults, (5) extensibility (ease of adding or deleting processors), and (6) ease of routing in the presence of faults. Some attempts directed at achieving near optimality for each of these six factors are discussed. A strategy for designing good networks with respect to all of these factors is suggested. Attempts to predict the real‐time robustness of systems are reviewed and commented on and the power and consistency of metrics associated with such attempts are discussed. The impact of communication structures is discussed with respect to fundamental fault‐tolerant objectives, such as diagnosis and disconnection of faulty units and establishment of a logical link between units not connected by a physical link. Current trends and suggested trends in communication network research are commented on. ©1993 by John Wiley & Sons, Inc.
Off‐line permutation routing on circuit‐switched fixed‐routing networks
Authors: Youssef Abdou 
Published: May 2007

AbstractCircuit‐switched fixed routing (CSFR) is an increasingly popular communication model wherein there is between every source—destination pair a single path that is system‐determined by a fixed‐routing rule. This paper studies the new problem of off‐line permutation scheduling on linear arrays, rings, hypercubes, and 2‐dimensional arrays, assuming the CSFR model. Optimal permutation scheduling involves finding a minimum number of subsets of nonconflicting source—destination paths. Every subset of paths can be established to run in one pass. In this paper, optimal permutation scheduling on linear arrays is shown to be linear, and on rings, NP‐complete. On hypercubes, the problem is NP‐complete. However, we will give an O(N log N) algorithm that routes any permutation in two passes if the model is relaxed to allow for two routing rules, namely, the so‐called e‐cube rule and the e−1‐cube rule. This complexity is reduced to O(N) hypercube‐parallel time. Finally, an O(N log2 N) bipartite‐matching‐based algorithm will be designed to schedule any permutation on p × q meshes/tori in q passes. © 1993 by John Wiley & Sons, Inc.
Most reliable double loop networks in survival reliability
Authors: Hu X. D. , Hwang F. K. , Li Wen‐Ch'Ing Winnie 
Published: May 2007

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

AbstractThis paper presents new procedures for obtaining upper and lower bounds in the cost minimization of multistage dynamic networks with random link capacities and contrasts them to existing methods. These methods include adaptation of Jensen's inequality to the problem, Monte‐Carlo simulations and an analytical approximation procedure. The new bounding procedures involve a backward pass in the network coupled with a linear approximation at each stage. Some numerical results are presented for networks of substantial size. © 1993 by John Wiley & Sons, Inc.
Sensitivity analysis in stochastic flow networks using the Monte Carlo method
Authors: Alexopoulos Christos , Fishman George S. 
Published: May 2007

AbstractConsider a flow network whose nodes do not restrict flow transmission and arcs have random, discrete, and independent capacities. Let s and t be a pair of selected nodes, let δ denote the value of a maximum s—t flow, and let Γ denote a set of s–t cuts. Also, let ℱ denote a set of independent joint capacity distributions with common state space. For fixed l < u, this paper develops methods for approximating the probability that l ≤ Δ < u and the probability that a cut in Γ is minimum given that l ≤ δ < u for each distribution in ℱ. Since these evaluations are NP‐hard problems, it shows how information obtained during an iterative procedure for computing the probability that l ≤ δ < u can be used for designing an efficient Monte Carlo sampling plan that performs sampling at few capacity distributions and uses sampling data to estimate the probabilities of interest at each distribution in ℱ. The set of sampling distributions is chosen by solving an uncapacitated facility location problem. The paper also describes techniques for computing confidence intervals and includes an algorithm for implementing the sampling experiment. An example illustrates the efficiency of the proposed method. This method is applicable to the computation of performance measures for networks whose elements have discrete random weights (lengths, gains, etc.) for a set of joint weight distributions with common state space. © 1993 by John Wiley & Sons, Inc.
The dynamic predicate stashing copy problem
Authors: Sansó Brunilde , Soumis François 
Published: May 2007

AbstractOne important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time‐changing information even in the event of failures. Recently, a technique called “stashing” was proposed. Stashing a file signifies placing a copy of that file in several nodes of the network. In addition, a “predicate” has been defined as a consistency requirement for a particular file copy with respect to the original. We address the problem of minimizing the propagation cost of stashed copies subject to predicate restrictions imposed by the user. In the version of the problem that we tackle, the user may receive a copy with a predicate better than requested. We call this problem the Dynamic Predicate Stashing Copy Problem (DPSCP) and propose a formulation to solve it. Resolution approaches, numerical results, and properties of the problem are also discussed. © 1993 by John Wiley & Sons, Inc.
A simple and fast label correcting algorithm for shortest paths
Authors: Bertsekas Dimitri P. 
Published: May 2007

AbstractWe propose a new method for ordering the candidate nodes in label correcting methods for shortest path problems. The method tries to scan nodes with small labels as early as possible and may be viewed as a low‐overhead approximation to Dijkstra's algorithm. Compared with the D'Esopo–Pape algorithm, our method is equally simple but much faster. Our method can also be combined with the threshold algorithm, thereby considerably improving its practical performance. © 1993 by John Wiley & Sons, Inc.
Improving the location of minimax facilities through network modification
Authors: Berman Oded , Ingco Divinagracia I. , Odoni Amedeo 
Published: May 2007

AbstractConsider a network on which one or more facilities are already located. We examine how the network can be modified most efficiently in order to improve the location of the facility when the measure of facility performance is the minimax objective. The types of possible network modifications fall into two categories: reductions in the length of existing arcs or additions of some new arcs that are not currently in the network. A set of reduction and addition problems is introduced for which exact or heuristic algorithms are presented. The principal objective of the paper is in defining and formulating the problems and not in testing the efficacy of the proposed solution methodologies. © 1994 by John Wiley & Sons, Inc.
Universal minimal total dominating functions in graphs
Authors: Cockayne E. J. , Mynhardt C. M. , Yu Bo 
Published: May 2007

AbstractA total dominating function (TDF) of a graph G = (V, E) is a function f: V → [0, 1] such that for each ν ϵ V, ΣuϵN(v) f(u) ⩾ 1 [where N(v) denotes the open neighborhood of vertex v]. Integer‐valued TDFs are precisely characteristic functions of total dominating sets of G. Convex combinations of two TDFs are themselves TDFs but convex combinations of minimal TDFs (MTDFs) are not necessarily minimal. This paper is concerned with the existence of a universal MTDF in a graph, i.e., a MTDF g such that convex combinations of g and any other MTDF are themselves minimal. © 1994 by John Wiley & Sons, Inc.
Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in Rd
Authors: Kalpakis Konstantinos , Sherman Alan T. 
Published: May 2007

AbstractThe Geometric Steiner Minimum Tree problem (GSMT) is to connect at minimum cost n given points (called terminals) in d‐dimensional Euclidean space. We generalize a GSMT approximation partitioning algorithm by Komlós and Shing (KS) and analyze its performance under more relaxed conditions. These generalizations have practical applications for multilayer VLSI routing. Whereas KS assumed d = 2, our algorithm works for any dimension d ⩾ 2. Moreover, whereas their analysis assumed the rectilinear norm and a uniform distribution of input points, our analysis holds for any norm on Rd and whenever the terminals are any independent identically distributed random variables taking on values in any bounded subset of Rd. Both algorithms depend on a parameter t through which the user can trade off time for solution quality. We evaluate our algorithm in terms of its performance ratio–the ratio of the cost of the Steiner tree computed by the algorithm divided by the cost of a Steiner minimum tree. Applying a probability theorem on subadditive Euclidean functionals by Steele, we prove the following: Under the aforementioned distribution of inputs, the limit as n → ∞ of the supremum of the performance ratio of our algorithm is 1 + Ot−1/d(d‐1), almost surely. This result generalizes the corresponding 1 + O(t−1/2) bound proven by KS. Along the way, we prove a useful combinatorial lemma about d‐dimensional rectangle slicings. We prove that the worst‐case time and space complexity of our algorithm is θ(n lg (n/t) + TMST(v, v) + nTSMT(t)/t) and θ(SMST(v, v) + SSMT(t)), respectively, where v ⩽ n + 2d+1 (n/t) σ(t) is the number of vertices in the resulting Steiner tree. Here, TSMT(t) and SSMT(t) are the time and space required to solve exactly any GSMT problem of size less than t; TMST(n, m) and SMST(n, m) are the time and space required to find a minimum spanning tree of a graph with n nodes and m edges; and σ(t) is the maximum number of Steiner points for any Steiner minimum tree with t terminals. For example, for R2 and the rectilinear norm, the time is O(n lg(n/t) + n lg*n + nTSMT(t)/t) and the space is O(n lg *n + SSMT(t)). © 1994 by John Wiley & Sons, Inc.
A separation decomposition for orders
Authors: Kämpke Thomas 
Published: May 2007

AbstractSeveral decomposition types of orders and related discrete structures have been investigated so far. In this paper, we present a decomposition for orders based on partial “ignoring” of the order. Structures that are in a certain sense “prime” turn out to be decomposable. The relation to other decomposition methods is analyzed. Bounds for activity networks and reliability functions are obtained. © 1994 by John Wiley & Sons, Inc.
Measures of vulnerability–the integrity family
Authors: Goddard Wayne 
Published: May 2007

AbstractIn this paper, a schema of graphical parameters is proposed. Based on the parameter integrity introduced by Barefoot, Entringer, and Swart, members Ψ(G) of this schema have the general form Ψ(G) = min {|S| + Ψ(G ‐ S) : S Ψ V (G)}, where Ψ(G) is another given graphical parameter. Examples include integrity, mean integrity, connectivity, and vertex cover number. General results and bounds for the schema are derived. Also, properties that characterize such parameters are considered. © 1994 by John Wiley & Sons, Inc.
Spanners in graphs of bounded degree
Authors: Cai Leizhen , Keil Mark 
Published: May 2007

AbstractGiven a graph G = (V, E), a subgraph S = (V, Es) is a t‐spanner of G if for every edge xy ϵ E the distance between x and y in S is at most t. Spanners have applications in communication networks, distributed systems, parallel computation, and many other areas. This paper is concerned with the complexity of finding a minimum size t‐spanner in a graph with bounded degree. A linear time algorithm is presented for finding a minimum‐size 2‐spanner in any graph whose maximum degree is at most four. The algorithm is based on a graph theoretical result concerning edge partition of a graph into a “triangle‐free component” and “triangular‐components.” On the other hand, it is shown that to determine whether a graph with maximum degree at most nine contains a t‐spanner with at most K edges (K is given) is NP‐complete for any fixed t ⩾ 2. © 1994 by John Wiley & Sons, Inc.
On reliability of graphs with node failures
Authors: Goldschmidt Olivier , Jaillet Patrick , Lasota Richard 
Published: May 2007

AbstractWe consider the reliability of graphs for which nodes fail independently of each other with a constant probability 1 ‐p. The reliability of a graph is defined to be the probability that the induced subgraph of surviving nodes is connected. A graph is said to be uniformly best when, for all choices ofp, it is most reliable in the class of graphs with the same number of nodes and same number of edges. In this paper, we first extend the existing known set of uniformly best graphs. Next, we show that most classes of sparse graphs do not contain a uniformly best graph. Finally, we introduce the important notions of locally best and asymptotically best graphs and illustrate these concepts with a detailed study of graphs having the same number of nodes and edges. © 1994 by John Wiley & Sons, Inc.
Compressing grids into small hypercubes
Authors: Miller Zevi , Sudborough I. H. 
Published: May 2007

AbstractLet G be a graph, and denote by Q(G)/2t the hypercube of dimension ⌈log2|G|⌉ − t. Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G → Q(G)/2t, t ⩾ 1, when G is any 2‐ or 3‐dimensional grid, with a view to minimizing communication delay and optimizing distribution of G‐processors in Q(G)/2t, Let dilation(f) = max {dist(f(x), f(y)): xyε(G)}, where “dist” denotes distance in the image network Q(G)/2t, and let the load factor of f be the maximum value of >f−1(h)| over all vertices hε(G)/2t. Our main results are the following: (1) Let G be any 2‐dimensional grid. Then, for any t ⩾ 1, there is a map f :G → Q(G)/2t having dilation 1 and load factor at most 1 + 2t. (2) Given certain upper bounds on the “densities” |G|/|Q(G)/4| or |G|/|Q(G)/8| of G in Q(G)/4 or Q(G)/8, respectively, we get dilation 1 maps f:G → Q(G)/4 or f:G → Q(G)/8 with improved (i.e., smaller) load factor over that given in (1). (3) Let G be any 3‐dimensional grid. Then, there is a map f:G → Q(G)/2 of dilation at most 2 and load factor at most 3, and a map f:G → Q(G)/4 of dilation at most 3 and load factor at most 5.
Efficient algorithms for minimum range cut problems
Authors: Katoh Naoki , Iwano Kazuo 
Published: May 2007

AbstractLetG = (V, E)be an undirected graph withnvertices andmedges such that a real‐valued weight, denoted byw(e), is associated with each edgee. This paper studies what we call the minimum range cut problem that asks to find a cut inGsuch that the range of all edge weights in the cut is minimum. Here, the range of a cutCis defined to be the maximum difference among weights of edges in the cut, i.e., maxeϵcw(e)‐ mineϵcw(e). This paper proposes anO(m + nlogn) algorithm for the minimum range cut problem. It is also shown that this running time is optimal. We also study two variants of this problem. One is the minimum range target cut problem. Given a prespecified value called a target, this problem asks to find a cut with minimum range among all cuts such that the target value is between the minimum and maximum of weights of edges in the cut. The second is the minimum ranges – tcut problem that asks to find ans – tcut with minimum range. This paper proposesO(m + nlogn) algorithms for these problems. For the second problem, we show that anancestor treeofO(n)space recently developed by Cheng and Hu effectively represents all pairs minimum range cuts, which can be constructed inO(n2)time, and enables us to answer any minimum ranges – tcut query inO(1)time [resp., inO(n)time] if we want to obtain only the range value of the cut (resp., the bipartition of vertices induced by the cut). © 1994 by John Wiley & Sons, Inc.
An algorithm for generating minimum cost network flow problems with specific structure and known optimal solutions
Authors: Arthur Jeffrey L. , Frendewey James O. 
Published: May 2007

AbstractA new algorithm for generating structured, minimum cost network flow problems (transshipment, transportation, assignment, and shortest path) with known optimal solutions is described. The procedure is based on developing problems around an optimal basis so that the characteristics of solutions can be controlled. Computational tests show that the problems generated are as difficult to solve as are those produced by the commonly used generator NETGEN, while allowing the user a much greater degree of control over the resulting problems. © 1994 by John Wiley & Sons, Inc.