bluuebunny/crossref_metadata_2025_split huggingface dataset:
A fast algorithm for reliability calculations in sparse networks
Authors: Spyratos N. , Bowen A. 
Published: May 2007

AbstractThe calculation of terminal reliability in other than simple series‐parallel networks takes time exponential in the size of the network. A method is presented for reducing network size by decomposing the network into subnetworks. Terminal reliability is obtained from calculations in the subnetworks. As the efficiency of the method depends on the network decomposition, some simple rules for selecting ‘good’ decompositions are presented.The method yields approximate values of terminal reliability. In sparse networks, however, the approximation is very satisfactory. Further, if the network decomposition satisfies certain conditions, exact values are obtained. Although the method assumes undirected links and perfectly reliable nodes, it can be easily extended to include directed links and failing nodes.
Graph substitution and set packing polytopes
Authors: Balas E. , Zemel E. 
Published: May 2007

AbstractFacets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one‐to‐one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G′ which are facet producing, i.e., which give rise to facets of P(G′) that cannot be obtained by lifting a facet of P(G′ ‐ {x}), for any vertex x of G′. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chvátal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet‐producing.
An assignment routing problem
Authors: Russell R. , Igo W. 
Published: May 2007

AbstractABSTRACTThis paper examines a routing design problem in which the objective is to assign customer demand points to days of the week in order to solve the resulting node routing problems over the entire week most effectively. The emphasis is on obtaining approximate solutions for this type of combinatorial problem. Several heuristics are developed and tested on a large scale refuse collection problem. Computational results, as well as a discussion of expected benefits, are presented.
On the construction of balanced switching networks
Authors: Hwang F. K. , Lin S. 
Published: May 2007

AbstractA balanced switching network is a multistage switching network where all channel graphs G(α, β) (the union of all paths from the input switch α to the output switch β) are isomorphic. In this paper we: (1) derive some necessary conditions for the existence of balanced switching networks realizing various types of channel graphs, (2) solve completely the problem of the construction of 3‐stage balanced switching networks, and (3) give a recursive procedure to construct a class of balanced switching networks with more than three stages.
Minimal broadcast networks
Authors: Farley A. M. 
Published: May 2007

AbstractBroadcast refers to the process of information dissemination in a communication network whereby a message, originated by one member, is transmitted to all members of the network. A minimal broadcast network is a communication network in which a message can be broadcast in minimum time regardless of originator. This paper describes several classes of minimal broadcast networks. An algorithm is presented which constructs minimal broadcast networks which have approximately the minimum number of lines possible.
The greedy travelling salesman's problem
Authors: Jenkyns T. A. 
Published: May 2007

AbstractThe Travelling Salesman's Problem is to find a Hamilton path (or circuit) which has minimum total weight W*, in a graph (or digraph) with a non‐negative weight on each edge. The Greedy Travelling Salesman's Problem is “How much larger than W* can the total weight G* of the solution obtained by the Greedy Algorithm be?”. Using the theory of independence systems, it is shown that G*‐W* may be as large as f(n,M,W*) where n is the number of vertices and M is the maximum edge‐weight. The function f is determined for the several variations of the Travelling Salesman's Problem and the bound is shown to be best possible in each case.
Network methods in models of production
Authors: Watson Donald 
Published: May 2007

AbstractThe author explores the ground common to the theories of electrical networks and economic networks by generalizing the notion of a Kirchhoff network of multiterminal elements to that of a Leontieff network of multiterminal elements. In this context the author introduces Le Chatelier's principle and proves a converse to it, derives a generalization of Tellegen's theorem, and discusses the inheritance by a composite element of the properties of its constituent elements. Two types of maximizing firms are then treated as multiterminal elements; the preceding theory is applied to them and to composite firms constructed from them.
The cyclic method of solving the transshipment problem with an additional linear constraint
Authors: Masch Victor V. 
Published: May 2007

AbstractThe “cyclic” method proposed in this paper provides a more efficient computational scheme than currently known adaptations of the simplex method for solving the transshipment problem with an additional linear constraint. Computer codes for the pure network problem can be easily altered to accommodate the cyclic method. Even more important, the cyclic method produces integral solutions at all iterations (except, possibly, the last one); this property may prove valuable in integer programming.
An algorithm for finding a short closed spanning walk in a graph
Authors: Takamizawa K. , Nishizeki T. , Saito N. 
Published: May 2007

AbstractA Hamiltonian walk of a graph is a closed spanning walk of minimum length. In this paper we generalize a Dirac type sufficient condition ensuring the existence of a Hamiltonian cycle to one ensuring the existence of a closed spanning walk of length less than a specified value. Furthermore, we present an O (p2 log p) algorithm for finding such a closed spanning walk in a graph with p vertices satisfying our condition.
Monotone sequences of graphical invariants
Authors: Harary Frank , Kabell Jerald A. 
Published: May 2007

AbstractWe investigate the extent to which certain graphical parameters can vary in successive point‐deleted subgraphs. In particular we identify one group of invariants which can be made to conform to an arbitrary monotone nondecreasing sequence and another group to a given nonincreasing sequence. Curiously, the two sets are not disjoint, as the line connectivity is in both. Finally we determine the most general sequences which can appear in this context.
Arc tolerances in shortest path and network flow problems
Authors: Shier D. R. , Witzgall Christoph 
Published: May 2007

AbstractThis paper studies one aspect of the “robustness” of optimal solutions to shortest path and, more generally, network flow problems. Specifically, we characterize the maximum increase and the maximum decrease in an arc's cost that can be tolerated without changing optimality of the current solution. Calculation of these quantities is quite simple for nonbasic arcs, and somewhat more involved for basic arcs. When such tolerances are to be determined simultaneously for all arcs in the network, considerable duplication of effort can be avoided through the use of specialized algorithms. Several algorithms for calculating all arc tolerances are presented, one of which is shown to have complexity order n2 for general networks with n nodes.
A dual algorithm for the constrained shortest path problem
Authors: Handler Gabriel Y. , Zang Israel 
Published: May 2007

AbstractIn this paper we develop a Lagrangian relaxation algorithm for the problem of finding a shortest path between two nodes in a network, subject to a knapsack‐type constraint. For example, we may wish to find a minimum cost route subject to a total time constraint in a multimode transportation network. Furthermore, the problem, which is shown to be at least as hard as NP‐complete problems, is generic to a class of problems that arise in the solution of integer linear programs and discrete state/stage deterministic dynamic programs. One approach to solving the problem is to utilize a kth shortest path algorithm, terminating with the first path that satisfies the constraint. This approach is impractical when the terminal value of k is large. Using Lagrangian relaxation we propose a method that is designed to reduce this value of k. Computational results indicate orders of magnitude savings when the approach is applied to large networks.
A cut approach to a class of quadratic integer programming problems
Authors: Picard Jean‐Claude , Ratliff H. Donald 
Published: May 2007

AbstractThis paper presents an algorithm for solving a class of quadratic integer programming problems. These problems include discrete versions of the quadratic placement problem and the squared Euclidean distance problem. The algorithm solves a sequence of at most Σ (ui ‐ li) minimum cut problems, or equivalently maximum flow problems, on a graph with n + 2 vertices where n is the number of variables in the problem, ui and li are upper and lower bounds, respectively, on the ith variable.
Covering and packing in graphs IV: Linear arboricity
Authors: Akiyama Jin , Exoo Geoffrey , Harary Frank 
Published: May 2007

AbstractThe linear arboricity of a graph is the minimum number of linear forests into which its lines can be decomposed. We find that the linear arboricity of every 4‐regular graph is 3. This result enables us to obtain bounds for the linear arboricity of any graph in terms of its maximum degree.
Networks immune to isolated failures
Authors: Farley Arthur M. 
Published: May 2007

AbstractThe notion of isolated failure immune (IFI) networks is introduced. A network is an IFI network if and only if all message transfers between operating sites can be completed as long as all site and line failures are isolated. Failures occurring at any time are isolated if they are pairwise isolated. A pair of site failures is isolated if the down sites are not neighbors. A pair of line failures is isolated if the lines are not incident to a common site. A site and a line failure are isolated if the down line is not incident to a neighbor of the down site. We show that 2‐trees are minimum IFI networks. An algorithm is described which adds lines to an arbitrary tree network to produce an IFI network (a 2‐tree). The algorithm also determines routing tables which allow a simple calling protocol to complete all message transfers between operative sites under isolated failures. Specializations and generalizations of our notion of IFI networks are discussed and issues for future research are proposed.
On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem
Authors: Frieze A. M. , Galbiati G. , Maffioli F. 
Published: May 2007

AbstractWe consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst‐case ratio of length of tour found to minimum length tour is (n) for n city problems. We also provide a new O([log2n]) heuristic.
Counting formulas for tree growth plans
Authors: Rowe Harrison E. , Mammel Wanda L. 
Published: May 2007

AbstractWe present counting formulas for the number of different ways to grow a given rooted tree, over a specified number of intervals. We call these growth plans, or simply plans. This problem arises, for example, in analog toll‐connect networks in which it is desired to introduce digital technology to serve increasing circuit requirements, in the cheapest way. Each circuit in such a network extends from a particular node called the toll center to one of the other nodes. The toll center corresponds to the root, and the portion of the network containing digital equipment corresponds to the rooted subtree whose growth we study. Even for networks of modest size and few growth intervals, the number of plans is too large to permit finding the cheapest by an exhaustive search. We observe that plans differing only in their growth pattern in the neighborhood of some particular node have cost differences that depend principally on their local growth patterns. It is therefore often possible to eliminate at a single stroke a large class of plans having a specified local growth plan at a particular node. By repetition, the number of remaining plans that must have their individual total costs computed can often be reduced to a number sufficiently small for an exhaustive search. We describe two types of local growth behavior appropriate for eliminating classes of plans in this network problem, and give corresponding counting formulas for the number of tree growth plans under these restrictions. A generalized counting formula with arbitrary local restrictions at each node is presented; this general formula contains the prior results as special cases. Finally, an example illustrates the great reduction in number of plans that can sometimes be obtained.
Locating mobile servers on a network with markovian properties
Authors: Berman Oded , Odoni Amedeo R. 
Published: May 2007

AbstractThe median problem has been generalized to the case in which facilities (“servers”) can be moved, at a cost, on the network in response to changes in the state of the network. Such changes are brought about by changes in travel times on the links of the network due to the occurrence of probabilistic events. For the case examined here, transitions among states of the network are assumed to be Markovian. The problem is examined for an objective which is a weighted function of demand travel times and of server relocation costs. It is shown that when these latter costs are a concave function of the time to travel from the current server location to the new server location, an optimal set of server locations exists solely on the nodes of the network. The location‐relocation problem can be formulated as an integer programming problem. The problem of locating a single server on a network which is a tree is shown to have a simple solution. A heuristic algorithm for the single server on a general network is also described. The paper develops simple bounds for the general multifacility, multistate problem and concludes with the description of a relaxed version of this model and with a discussion of the model's applicability.
Networks immune to isolated line failures
Authors: Farley Arthur M. , Proskurowski Andrzej 
Published: May 2007

AbstractA network is immune to a set of failures if all message transfers between operative sites can be completed in the presence of such failures. A set of line failures is isolated if no two failing lines are incident to the same site. Several classes of isolated line failure immune (ILFI) networks are defined, including a class with fewest lines for a given number of sites. An algorithm is presented which turns an arbitrary tree into one of these minimum ILFI networks and computes routing tables for the new network.
On a measure of communication network vulnerability
Authors: Exoo Geoffrey 
Published: May 2007

AbstractA measure of communication network vulnerability was studied in a recent article by Boesch, Harary, and Kabell. The persistence (line persistence) is the minimum number of points (lines) whose removal from a graph increases its diameter. Their approach differed from earlier work on this topic in that they examined the analogs of Menger's theorem for these invariants. A result of Lovász, Neumann‐Lara, and Plummer is used to prove modified versions of their theorems (the original proofs are incorrect). Some related problems are also solved, including one posed by Hartman and Rubin.
Routing past unions of disjoint linear barriers
Authors: Chein Orin , Steinberg Leon 
Published: May 2007

AbstractGiven a disjoint planar set, {Li, = PiQi, i = 1,…, n}, of line segments called barriers, we consider the question of finding a path Γ of minimal length which connects two given points A and B and which does not “cut” any of the barriers. In Section III we show that such a minimal path exists and that it is polygonal with its bend points lying in W = {Pi, Qi: i = 1,…, n}. The problem is thus reduced to finding the shortest path between two points A and B in an approximate network with vertex set V = W ∪ {A, B}. The latter can be solved by a network routing algorithm such as Dantzig's. Section IV presents Algorithms for reducing the size of the network.
Finding a manhattan path and related problems
Authors: Lipski Witold 
Published: May 2007

AbstractLet S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k) from s to t is an alternating sequence of horizontal and vertical segments s = r0, r1,…,rk = t where ri intersects ri+1, 0 ≤ i < k. An from all s ∈ S to t. Also given is a method to determine a maximum set of crossings (intersections of segments) with no two on the same segment, as well as a maximum set of nonintersecting segments, both in O(n3/2 log2 log2 n) time. The latter algorithm is applied to decomposing, in O(n3/2 log2 n) time, a hole‐free union of n rectangles with sides parallel to the coordinate axes into the minimal number of disjoint rectangles. All the algorithms require O(n log n) space, and for all of them the factor log2 n can be improved to log n log log n, at the cost of some complication of the basic data structure used.
An analysis of alternative strategies for implementing matching algorithms
Authors: Ball Michael O. , Derigs Ulrich 
Published: May 2007

AbstractIn this paper we explore implementation issues related to the solution of the weighted matching problem defined on an undirected graph G = (V, E). We present algorithms based on the two different linear characterizations of the feasible solutions to the matching problem. Furthermore, we present two specialized implementations, one with an O (|V|3) time bound and one with an O(|V‖E| log |V|) time bound. Both of these implementations have storage requirements that are linear in |V| and |E|. We initially develop these algorithms as special implementations of the well‐known primaldual (blossom) algorithm and then show how the updates they perform have an interesting interpretation when the algorithms are viewed as methods that successively find shortest augmenting paths. Finally, we show that postoptimality analysis can be performed very efficiently within this setting.
Graphs with the smallest number of minimum cut sets
Authors: Smith Derek 
Published: May 2007

AbstractThe number of vertex cut sets of size k in a graph of connectivity k has been used as a measure of network reliability. Let G be a regular graph with N vertices, valency k, connectivity k, and with the minimum number of vertex cut sets with k vertices. The problem of constructing such a graph G for each pair (N, k) is known to be difficult. We show how to construct infinite families of such graphs in various cases. These cases are spread through the range 3/8 ≤ k/N <1. We also deal with cases in which k is small and cases with N ‐ k small.
a generalized network flow model with application to power supply‐demand problems
Authors: Liu Chen‐Ching , Wu Felix F. 
Published: May 2007

AbstractThe conventional network flow model is generalized by replacing the capacity constraints on the flow of each arc by a constraint that the set of flows lies in a compact set; the resulting model is called the compact flow network model. A necessary condition for the maximal compact flow is presented. The max‐flow‐min‐cut theorem is generalized to compact flow networks. The condition that is required for the maximal flow to be equal to the minimal cut is examined. The max‐flow‐min‐cut theorem is used to derive a necessary and sufficient condition for feasibility of the multiterminal supply‐demand problem based on the compact flow model. As an application, the electric power supply‐demand problem is discussed from the compact flow point of view.
The amount of overtaking in a network of queues
Authors: Whitt Ward 
Published: May 2007

AbstractCustomer B overtakes customer A in a queueing system if A arrives before B but B departs first. To understand the phenomenon of overtaking in a network of queues and its impact on sojourn times, it is important to develop concepts of the amount of overtaking. In this paper, two stochastic measures of the amount overtaking are defined: the random number of customers overtaken by an arbitrary customer and the random permutation of the original order of n customers upon departure. Describing these measures, however, often presents rather difficult combinatorial and probabilistic problems. In this paper, we make several conjectures about the amount of overtaking in open Jackson networks and its impact on sojourn times. Then we describe the amount of overtaking in several smaller networks, for example, a single node with the first‐come first‐served discipline and instantaneous Bernoulli feedback.
Heuristics for finding a maximum number of disjoint bounded paths
Authors: Ronen D. , Perl Y. 
Published: May 2007

AbstractWe consider the following problem: Given an integer k and a network G with two distinct vertices s and t, find a maximum number of vertex disjoint paths from s to t of length bounded by k. In a recent work [9] it was shown that for length greater than four this problem is NP‐hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved to give optimal solution for length less than five. Experiments show very good results for the algorithm.
Steiner trees, connected domination and strongly chordal graphs
Authors: White Kevin , Farber Martin , Pulleyblank William 
Published: May 2007

AbstractWe consider Steiner tree problems and connected dominating set problems for several classes of graphs. We give a polynomial algorithm and a min‐max theorem for the cardinality Steiner problem in strongly chordal graphs and a polynomial algorithm for the weighted connected dominating set problem in series‐parallel graphs. We establish simple direct transformations between Steiner problems and connected domination problems for several classes of graphs and establish related NP‐completeness results.
A factoring algorithm using polygon‐to‐chain reductions for computing K‐terminal network reliability
Authors: Wood R. Kevin 
Published: May 2007

AbstractLet G = (V,E) be an undirected graph whose edges may fail, and let Gk denote G with a set k ⊆ V specified. Edge failures are assumed to be statistically independent and to have known probabilities. The k‐terminal reliability of Gk, denoted R(Gk), is the probability that all vertices in k are connected by working edges. Computing k‐terminal reliability is an NP‐hard problem not known to be in NP. A factoring algorithm for computing network reliability recursively applies the formula R(Gk) = PiR(Gk′*ei + qiR(Gk − ei)), where Gk′*ei is Gk with edge ei contracted, Gk − ei is Gk with ei deleted and pi = 1 − qi is the reliability of edge ei. Various reliability‐preserving reductions may be performed after each factoring operation in order to reduce computational complexity. The complexity of a slightly restricted factoring algorithm using standard reductions, along with newly developed polygon‐to‐chain reductions, will be bounded below by an invariant of G, the “minimum domination.” For 2 ≤ ∣K∣ ≤ 5 or ∣V∣ − 2 ≤ ∣K∣ ≤ ∣V∣, this bound is always achievable. The factoring algorithm with polygon‐to‐chain reductions will always perform as well as or better than an algorithm using only standard reductions, and for some networks, it will outperform the simpler algorithm by an exponential factor. This generalizes early results that were only valid for K = V. Removing the restriction on edge selection leaves results essentially unchanged in the upper range of ∣K∣, but minimum domination becomes only a tight upper bound for the lower range.