bluuebunny/crossref_metadata_2025_split huggingface dataset:
Transformations for simplifying network reliability calculations
Authors: Rosenthal A. , Frisque D. 
Published: May 2007

AbstractAll known methods for calculating the connection probability for two vertices of an unreliable network take time exponential in the size of the network. A method is presented for reducing network size by transforming three‐terminal subnetworks into Y‐shaped networks, thus reducing terminal degrees and possibly creating series combinations which can be reduced to a single edge. Previously defined transformations were approximate, restricted to triangles, and required perfect terminals. The transformations given here are exact, apply to any three‐terminal subnetwork with perfect terminals, and permit the inclusion of unreliable terminals which are incident to one external edge. In addition, transformations for reducing certain networks with directed edges, and transformations for eliminating positive failure correlations are discussed.
A shortest path algorithm for grid graphs
Authors: Hadlock F. O. 
Published: May 2007

AbstractGrid graphs are a simple class of planar graphs for which the vertices can be assigned integer coordinates so that neighbors agree in one coordinate and differ by one in the other coordinate. Grid graphs arise in applications from the layout design of integrated circuits to idealized models of city street networks. In many applications, a shortest path between two given vertices is needed. The best known algorithms for the shortest path in a general graph of n vertices are of complexity 0(n2). However, if edge lengths are of uniform length, the shortest path can be determined in time 0(n). In this paper, taking advantage of the concept of direction present in grid graphs, an algorithm is developed which is 0(n) in the worst case and 0(√n) in the best case.
Multicommodity network flows—A survey
Authors: Assad A. A. 
Published: May 2007

AbstractThis report aims at a comprehensive survey of the literature dealing with the multicommodity flow problem. This problem arises naturally in network modelling wherever commodities, vehicles, or messages are to be shipped or transmitted from certain nodes of an underlying network to some others. Recent applications of mathematical programming techniques to traffic equilibrium problems in transportation studies as well as computer networks analysis has renewed considerable interest in this problem.This report discusses solution techniques for both linear and nonlinear flow problems. The former includes decomposition, partitioning, compact inverse methods, and primal‐dual algorithms. We describe a variety of feasible direction methods for the latter. The report concludes by giving applications and computational experience for both types of problems.
A note on bisecting minimum spanning trees
Authors: Boyce W. M. , Garey M. R. , Johnson D. S. 
Published: May 2007

AbstractLet A be a finite set of points in a Euclidean space Er and M a minimum spanning tree (MST) for A, regarded as a subset of Er. If A′ ⊂ Er is a finite subset of M, then M is a spanning tree for A ∪ A′, but in general M will no longer be an MST. However, if A′ is chosen to be the set of all the midpoints of the line segments of M, then M will be an MST for A ∪ A′. Examples are given in which at least |A| ‐ 1 points must be adjoined to avoid destroying the MST.
The complexity of the capacitated tree problem
Authors: Papadimitriou C. H. 
Published: May 2007

AbstractWe examine the complexity of a classical problem related to the design of centralized computer networks. Under very broad assumptions the problem is shown to be NP‐complete, and hence most probably intractable. The same result holds for the “Euclidean” case of the problem; however, in the latter case a simple algorithm produces solutions with relative error almost certainly arbitrarily close to zero.
Primal simplex network codes: State‐of‐the‐art implementation technology
Authors: Ali A. I. , Helgason R. V. , Kennington J. L. , Lall H. S. 
Published: May 2007

AbstractIn recent years there have been several extremely successful specialization of the primal simplex method for solving network flow problems. Much of this success is due to the development of highly efficient computational techniques for implementing the primal simplex algorithm. We view these efficient techniques as a new body of knowledge which we call implementation technology. This exposition presents the state‐of‐the‐art of implementation technology.
Adjacent extreme flows and application to min concave cost flow problems
Authors: Gallo G. , Sodini C. 
Published: May 2007

AbstractIn this paper an algorithm is presented which, given an extreme flow on a Network, enumerates all its neighboring extreme flows. The algorithm is based on a graph theoretic characterization of the adjacency relationship. The relevance of finding the set of extreme flows adjacent to a given one is discussed from the point of view of concave optimization on Networks.
On algorithms for finding the k shortest paths in a network
Authors: Shier D. R. 
Published: May 2007

AbstractThis paper presents, within a unified framework, several new algorithms for computing k shortest paths in a network. These algorithms utilize strategies which have proved to be efficient in solving shortest path problems. In addition, a computational study was conducted to assess the effects of the different “arc processing” orders which are characteristic of each algorithm. Testing was performed using generated classes of moderately large grid, complete and random networks. Two particular algorithms emerge as the most promising among those evaluated.
A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
Authors: Dial R. , Glover F. , Karney D. , Klingman D. 
Published: May 2007

AbstractThis paper examines different algorithms for calculating the shortest path from one node to all other nodes in a network. More specifically, we seek to advance the state‐of‐the‐art of computer implementation technology for such algorithms and the problems they solve by exmining the effect of innovative computer science list structures and labeling techniques on algorithmic performance.The study shows that the procedures examined indeed exert a powerful influence on solution efficiency, with the identity of the best dependent upon the topology of the network and the range of the arc distance coefficients. The study further discloses, for the problems tested, that the lable‐setting shortest path algorithm previously documented as the most efficient is dominated for all problem structures examined by the new methods.
Minimizing maximum flows in linear graphs
Authors: Stanat D. F. , Magó G. A. 
Published: May 2007

AbstractWe define a linear graph to be a connected acyclic graph each of whose nodes is of degree one or two. We consider a flow problem in linear graphs in which a commodity flows from source nodes to sink nodes. Each source node has a specified value denoting an amount of a commodity to be disposed of and each sink node has a specified capacity denoting the maximum amount of the commodity it can absorb; edges are capable of carrying an arbitrary quantity of the commodity. A solution is a set of flows which transports the commodity from all source nodes to sink nodes without overfilling any sink. A solution is defined to be optimal if it is minimax, that is, the largest flow along any edge is as small as possible. We describe 0(n2) and 0(n) algorithms for finding optimal solutions.
Maximum degree in graphs of diameter 2
Authors: Erdös Paul , Fajtlowicz Siemion , Hoffman Alan J. 
Published: May 2007

AbstractIt is well known that there are at most four Moore graphs of diameter 2, i.e., graphs of diameter 2, maximum degree d, and d2 + 1 vertices. The purpose of this paper is to prove that with the exception of C4, there are no graphs of diameter 2, of maximum degree d, and with d2 vertices.
Total domination in graphs
Authors: Cockayne E. J. , Dawes R. M. , Hedetniemi S. T. 
Published: May 2007

AbstractA set D of vertices of a finite, undirected graph G = (V, E) is a total dominating set if every vertex of V is adjacent to some vertex of D. In this paper we initiate the study of total dominating sets in graphs and, in particular, obtain results concerning the total domination number of G (the smallest number of vertices in a total dominating set) and the total domatic number of G (the largest order of a partition of G into total dominating sets).
A comparison of three algorithms for finding fundamental cycles in a directed graph
Authors: Ryan Doris R. , Chen Stephen 
Published: May 2007

AbstractGiven a connected directed graph and a spanning tree, we consider the problem of finding the set of fundamental cycles. In particular, for each cotree arc i and tree arc j, we need to know whether or not i and j are in the same fundamental cycle, and if so, whether or not arcs i and j are oriented in the same direction. This problem has application in primal network flow, longest cycle, and all‐cycle algorithms. In this paper, we describe and compare three algorithms for finding fundamental cycles. Computational results are presented on a variety of directed graphs produced by a network generator. Although each of the algorithms has worst case complexity O(kp), where k and p are the number of cotree arcs and nodes, respectively, a variation of a root traceback algorithm is shown to be the fastest in almost all cases.
State‐space relaxation procedures for the computation of bounds to routing problems
Authors: Christofides Nicos , Mingozzi A. , Toth P. 
Published: May 2007

AbstractIt is well‐known that few combinatorial optimization problems can be solved effectively by dynamic programming alone, since the number of vertices of the state space graph is enormous. What we are proposing here is a general relaxation procedure whereby the state‐space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem. This state space relaxation method is analogous to Langrangian relaxation in integer programming. This paper gives a survey of this new methodology, and gives, as examples, applications to the traveling salesman problem (TSP), the time‐constrained TSP and the vehicle routing problem (VRP). Valid state space relaxations are discussed for these problems and several bounds are derived in each case. Subgradient optimization and “state space ascent” are discussed as methods of maximizing the resulting lower bounds. More details of the procedures surveyed in this paper can be found in [2, 3, 4].
A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theory
Authors: Picard Jean‐Claude , Queyranne Maurice 
Published: May 2007

AbstractA network flow technique is used to solve the unconstrained nonlinear 0‐1 programming problem, which is maximizing the ratio of two polynomials, assuming that all the nonlinear coefficients in the numerator are non‐negative and all the nonlinear coefficients in the denominator are nonpositive. Two examples are an investment selection problem to maximize the rate of return, and a decomposition approach to a scheduling problem studied by Sidney and Lawler. The proposed algorithm requires the solution of a sequence of minimum‐cut problems in a related network, and can be extended to some more general problems of the same type. This approach is also applied to find the density of a graph (the maximum ratio, among its subgraphs, of the number of edges to the number of nodes) and its arboricity, for which polynomial algorithms are described. It is also useful in providing a bounding scheme for the maximum‐clique and vertex packing problems.
A 1‐matching blossom‐type algorithm for edge covering problems
Authors: Murty Katta G. , Perin Clovis 
Published: May 2007

AbstractWe discuss an efficient primal‐dual algorithm for finding a minimum cost edge cover in an undirected network G with n nodes and m edges, which is based on the blossom algorithm for 1‐matching problems. We establish that its worst case computational complexity is O(n3), the same as that for blossom or primal algorithms for 1‐matching problems.
An efficient algorithm for K shortest simple paths
Authors: Katoh N. , Ibaraki T. , Mine H. 
Published: May 2007

AbstractThis article gives an efficient algorithm for obtaining K shortest simple paths between two specified nodes in an undirected graph G with non‐negative edge lengths. Letting n be the number of nodes and m be the number of edges in G, its running time is O(Kc(n, m)) if the shortest paths from one node to all the other nodes are obtained in c(n, m) [≥O(m)] time, and the required space is O(Kn + m). This time bound is better than those realized by existing algorithms, the best of which, proposed by Yen, requires O(Kn3) time, since c(n, m) ≤min[O(n2), O(m log n)] is known.
Circular permutation graphs
Authors: Rotem D. , Urrutia J. 
Published: May 2007

AbstractA new class of intersection graphs called circular permutation graphs is introduced and characterized. A circular permutation diagram for a permutation P(1),…,P(n) consists of two circles C1 and C2; the numbers 1′, 2′,…,n′ and P(1),…,P(n) on C1 and C2, respectively; and a set of n chords 1, 2,…, n connecting i to i′ such that two chords intersect each other at most once. A graph G represents a circular permutation diagram if there is a labeling of V(G) with {1,…, n} such that i is adjacement to j iff i and j intersect. Graphs which represent at least one permutation diagram are called circular permutation graphs. Circular permutation graphs generalize permutation graphs [2], [8] and are embedded in the set of comparability graphs [4]. The characterization leads to a recognition algorithm which requires O(δ|E|) steps where δ is the maximum degree of a vertex.
Efficient algorithms for interval graphs and circular‐arc graphs
Authors: Gupta U. I. , Lee D. T. , Leung J. Y.‐T. 
Published: May 2007

AbstractWe show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.
Preselective strategies for the optimization of stochastic project networks under resource constraints
Authors: Igelmund G. , Radermacher F. J. 
Published: May 2007

AbstractThis article deals with a stochastic version of the optimization problem for project networks under resource constraints. In this, activity durations are assumed to be realized according to some joint probability distribution and the aim of optimization is to minimize the expected overall project cost (monotonically increasing with project duration). Certain strategies are known that constitute feasible solutions to this problem, the best studied of which are the so‐called ES strategies (“earliest start” with regard to fixed project structures). In this paper, a considerably broader class of strategies is introduced, namely preselective strategies. It is shown that this generalization, for which an algorithmic approach remains possible, preserves almost all the desirable behavior known for ES strategies. In particular, the number of “essential” strategies remains finite and even minimal optimum‐determining sets of such strategies can, in general, be characterized. Also, the analytic behavior is still proper and there is considerable “stability” to weak convergence of the joint distribution of activity durations as well as to a. e. convergence of the cost function. Last but not least, possible generalization to arbitrary regular cost functions is again imminent.
Steiner trees, partial 2–trees, and minimum IFI networks
Authors: Wald Joseph A. , Colbourn Charles J. 
Published: May 2007

AbstractMinimum isolated failure immune networks are shown to be 2–trees. Further, subgraphs of 2‐trees are shown to be exactly those graphs which contain no subgraph homeomorphic to the four‐vertex complete graph. Together, these two characterizations yield a linear time algorithm for adding lines to a network to produce a minimum isolated failure immune network, whenever this is possible. This same algorithm, in conjunction with a linear time Steiner tree algorithm for 2‐tress, yields a linear time Steiner tree algorithm for partial 2‐tress. This contrasts with the known NP‐completeness of the Steiner tree problem for planar graphs.
Centralized teleprocessing network design
Authors: Kershenbaum Aaron , Boorstyn Robert R. 
Published: May 2007

AbstractThe problem considered is that of finding an optimal (minimum cost) design for a centralized processing network given a set of locations, traffic magnitudes between these locations, and a single common source or destination. Several heuristics, which are efficient (in terms of their execution time and memory requirements on a digital computer) and which produce seemingly good results, have already been developed and are currently accepted techniques. Some work has also been done on finding optimal solutions to this problem both as a design tool and as a means of verifying the effectiveness of proposed heuristics. We focus on this latter area. Currently known techniques for the optimal solution of this problem via integer programming have fallen short of the desired objectives as they require too much memory and running time to be able to treat problems of realistic size and complexity. We develop an improved technique which is capable of handling more realistic problems.
Optimal I‐Intersection assignments for graphs: A linear programming approach
Authors: Opsut Robert J. , Roberts Fred S. 
Published: May 2007

AbstractAn intersection assignment for a graph is the assignment of a set to each vertex so that edges correspond to pairs of sets which overlap. Intersection assignments are studied in which each set is a real interval, perhaps of specified minimum length. In particular, linear programming methods are used to see how to minimize the measure of the union of intervals in such an assignment, and how to maximize the sum of the lengths of the intervals in such an assignment. The results have application to a variety of scheduling problems.
A survey of heuristics for the weighted matching problem
Authors: Avis David 
Published: May 2007

AbstractThis survey paper reviews results on heuristics for two weighted matching problems: matchings where the vertices are points in the plane and weights are Euclidean distances, and the assignment problem. Several heuristics are described in detail and results are given for worst‐case ratio bounds, absolute bounds, and expected bounds. Applications to practical problems and some mathematical complements are also included.
On the np‐completeness of certain network testing problems
Authors: Even S. , Goldreich O. , Moran S. , Tong P. 
Published: May 2007

AbstractLet G(V, E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints to be a transmitter, the other to be a receiver, and sending a message from the transmitter to the receiver through the line. We define several different models for communication networks, all subject to the two following axioms: a vertex cannot act as a transmitter and as a receiver simultaneously and a vertex cannot receive through two lines simultaneously. In each of the models, two problems arise: What is the maximum number of lines one can test simultaneously? and What is the minimum number of phases necessary for testing the entire network?, where, by “phase” we mean a period in which some tests are conducted simultaneously. We show that in most models, including the “natural” model of radio communication, both problems are NP‐hard. In some models the problems can be solved by reducing them to either a maximum matching problem or an edge coloring problem for which polynomial algorithms are known. One model remains for which the complexity of the minimization problem is unknown.
An algorithm for the steiner problem in graphs
Authors: Beasley J. E. 
Published: May 2007

AbstractIn this paper we consider the Steiner problem in graphs. This is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph. We present two lower bounds for the problem, these bounds being based on two separate Lagrangian relaxations of a zero‐one integer programming formulation of the problem. Problem reduction tests derived from both the original problem and the Lagrangian relaxations are given. Incorporating the bounds and the reduction tests into a tree search procedure enables us to solve problems involving the connection of up to 50 vertices in a graph with 200 undirected arcs and 100 vertices.
Shortest‐path methods: Complexity, interrelations and new propositions
Authors: Pallottino Stefano 
Published: May 2007

AbstractWe present a new unified approach for shortest‐path problems. Based on this approach, we develop a computational method which consists of determining shortest paths on a finite sequence of partial graphs defined as the “growth of the original graph.” We show that the proposed method allows us to interpret within the same framework several different well‐known algorithms, such as those of D′Esopo‐Pape, Dijkstra, and Dial, and leads to a uniform analysis of their computational complexity. We also stress the existing parallelism between the proposed method and the matrix‐multiplication methods of Floyd‐Warshall, and Dantzig.
A quick method for finding shortest pairs of disjoint paths
Authors: Suurballe J. W. , Tarjan R. E. 
Published: May 2007

AbstractLet G be a directed graph containing n vertices, one of which is a distinguished source s, and m edges, each with a non‐negative cost. We consider the problem of finding, for each possible sink vertex v, a pair of edge‐disjoint paths from s to v of minimum total edge cost. Suurballe has given an O(n2 logn)‐time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs in O(m log(1+ m/n)n) time and O(m) space. Our algorithm builds an implicit representation of the n pairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink is O(1) per edge on the paths.
On computing the connectivities of graphs and digraphs
Authors: Esfahanian Abdol H. , Louis Hakimi S. 
Published: May 2007

AbstractIn this paper methods are described that will compute the edge‐connectivity of a graph or a digraph at least twice as fast as the known methods. A study of the computation of the vertex‐connectivity is presented which leads to new algorithms for this purpose or for the purpose of determining if the vertex‐connectivity is at least k. These algorithms compare favorably with Kleitman's, Even's, Even and Tarjan's, and Galil's algorithms.