bluuebunny/crossref_metadata_2025_split huggingface dataset:
Shortest path problems with node failures
Authors: Jaillet Patrick 
Published: May 2007

AbstractConsider 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

AbstractIn 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

AbstractLet 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

AbstractA 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

AbstractWe 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

AbstractThree 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

AbstractWe 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

AbstractWe 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

AbstractIn 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

AbstractA 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

AbstractWe 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

AbstractA 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

AbstractWe 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

AbstractLehman 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

AbstractLet 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

AbstractThis 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

AbstractIn 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

AbstractLet 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

AbstractThe 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

AbstractGiving 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

AbstractEmulations 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

AbstractFor 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

AbstractLet 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

AbstractThe 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

AbstractBroadcasting 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

AbstractIn 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

AbstractAn 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

AbstractLet 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

AbstractLet 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

AbstractThis 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

AbstractSome 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.