bluuebunny/crossref_metadata_2025 huggingface dataset:
Lower bounds on the vulnerability of a graph
Authors: Boesch F. T.
Published: May 2007

It is well known that the size of the smallest node‐cut (connectivity‐ω) and the size of the smallest edge‐cut (cohesion‐λ) can be used as vulnerability measures of a graph. Algorithms for finding ω and λ involve the determination of many paths and therefore require a fair amount of computation. However, it is clear that, if a graph has “relatively large” degrees, then ω and λ cannot be “too small”. Furthermore, the degrees of the nodes are a most readily available set of parameters for any graph. Hence, any lower bounds based on the degrees is extremely valuable.

Prior results on these types of bounds are collected here. A few new results are also derived. In all cases the bounds are quite simple and can easily be obtained by hand calculations for extremely large graphs.
On the design of reliable networks
Authors: Hakimi S. L. , Amin A. T.
Published: May 2007

This paper is concerned with construction of graphs, with n vertices and m edges, whose connectivity r = [2m/n] ≧ 3, and have no more than n minimum vertex cut‐sets. Frank's results imply that this is an important step in the design of a class of reliable networks.
On operating a shuttle service
Authors: Barnett A.
Published: May 2007

A vehicle shuttles between two terminals, at which passengers are arriving in a Poisson manner at given rates. Travel time between the stops is assumed deterministic. This paper considers the question of what operating strategy will yield lowest average waiting time for passengers of the system. Exact solutions to the problem are obtained, and it is found that the optimal strategy is a somewhat complex but very tractable function of the two Poisson arrival parameters.
Networks and vehicle routing for municipal waste collection
Authors: Beltrami E. J. , Bodin L. D.
Published: May 2007

Vehicle routing for municipal waste collection encompasses a variety of problems. In this paper, we explore the techniques we have developed for solving some of these problems.
Modeling and optimal control of congested transportation systems
Authors: Gazis D. C.
Published: May 2007

An approach is discussed for the modeling of congested transportation systems as store‐and‐forward networks analogous to communication networks of this type but with a finite travel time between nodes. A variety of approaches is suggested, and illustrated by examples, for the allocation of the usage of the arcs of the network by various competing units of traffic.
Disjoint paths in a network
Authors: Suurballe J. W.
Published: May 2007

Routes between two given nodes of a network are called diversified if they are node‐disjoint, except at the terminals. Diversified routes are required for reliability in communication, and an additional criterion is that their total cost, assumed to be the sum of individual arc lengths or costs, is minimum. An algorithm and related theory is described for a general number K of node‐disjoint paths with minimum total length. The algorithm applies shortest path labeling algorithms familiar in the literature. K node‐disjoint paths are found in K iterations of a single shortest path algorithm.
Computing capacitated minimal spanning trees efficiently
Authors: Kershenbaum A.
Published: May 2007

An analysis is made of the computational complexity of a class of heuristic algorithms for the solution of the minimal spanning tree problem subject to a restriction on the maximum number (or weight) of nodes in any subtree rooted at a distinguished node. This is of particular interest in designing networks with branch capacity restrictions. The algorithm is a modification of Kruskal's Algorithm where weights are assigned to the nodes and then used, along with the arc lengths, to select the order in which arcs are considered for inclusion in the spanning tree. Considerations in the efficient implementation of such algorithms are examined and several heuristics for assigning node weights are compared.
Hydraulic network analysis using (generalized) geometric programming
Authors: Hall M. A.
Published: May 2007

The problem of determining the flows (and pressures) in the pipes of a general hydraulic network, for given input and output flows and/or given input and output pressure heads, is shown to be equivalent to either of a pair of convex programming problems with linear constraints. This is accomplished via the theory of (generalized) Geometric Programming. The equivalence of these problems is exploited to prove existence and uniqueness of the flow solution under certain conditions as well as to derive an algorithm which calculates this solution. Computational aspects of implementing the algorithm are considered in some detail and results obtained for a general example problem are presented. A brief discussion of the application of the methods of the paper to problems in electrical network analysis, transportation network analysis and the elastic analysis of structural trusses, is also given.
An efficient scaling procedure for gain networks
Authors: Truemper K.
Published: May 2007

A simple and efficient procedure is presented which scales a network with gains to an equivalent one with positive or unit gains, provided certain necessary and sufficient conditions are satisfied.
On cost allocation for a spanning tree: A game theoretic approach
Authors: Bird C. G.
Published: May 2007

Cooperative game theory solution concepts are used to allocate costs in a spanning tree network. Stable cost allocations are related to the core of a cooperative game and it is proved that every game generated from a minimum cost spanning tree with an immovable source has a core. A refinement of the core, called the irreducible core, is introduced and the extreme points of the solution can be characterized by permutations of the minimal cost spanning tree. Points in the irreducible core are shown to be stable under unions of additional players. A weighted Shapley value is used to obtain a unique allocation of costs. This value coincides with the marginal costs of the spanning tree when there is only one minimal spanning tree. When multiple sources are allowed, counterexamples to the existence of a core are presented unless extra taxes are levied on the users.
On totally unimodular matrices
Authors: Tamir A.
Published: May 2007

Conditions for a matrix to be totally unimodular, due to Camion, are applied to extend and simplify proofs of other characterizations of total unimodularity.
Finding optimum branchings
Authors: Tarjan R. E.
Published: May 2007

Chu and Liu, Edmonds, and Bock have independently devised an efficient algorithm to find an optimum branching in a directed graph. We give an implementation of the algorithm which runs in 0(m logn) time if the problem graph has n vertices and m edges. A modification for dense graphs gives a running time of 0(n2). We also show that the unmodified algorithm runs in 0(n(log n)2 +m) time on an average graph, assuming a uniform probability distribution.
Transformations for simplifying network reliability calculations
Authors: Rosenthal A. , Frisque D.
Published: May 2007

All 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

Grid 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

This 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

Let 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

We 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

In 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

In 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

This 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

This 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

We 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

It 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

A 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

Given 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

It 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].
Formulation and structure of more complex/realistic routing and scheduling problems
Authors: Schrage Linus
Published: May 2007

We classify the features that seem to be encountered in real vehicle routing problems. Given these features, we try to indicate which features cause the greatest difficulty and which modeling approaches allow us to represent the greatest range of practical considerations or features.
A polynomial time algorithm for finding the absolute center of a network
Authors: Minieka Edward
Published: May 2007

The absolute center of a network is any vertex or point on an edge such that the distance from it to the vertex farthest from it is as small as possible. This paper presents a polynomial time algorithm for finding an absolute center. This algorithm is combinatorial in nature and requires only knowledge of the shortest path distances between all pairs of vertices.
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

A 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.
Decentralized maximum‐flow protocols
Authors: Segall Adrian
Published: May 2007

This article presents three protocols for obtaining maximum flow in a network by using distributed computation. Each node in the network has memory and processing capabilities and coordinates the algorithm with its neighbors by means of control messages. In the order presented, each protocol employs less communication than the previous one, but requires more time and node computation.
A 1‐matching blossom‐type algorithm for edge covering problems
Authors: Murty Katta G. , Perin Clovis
Published: May 2007

We 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

This 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

A 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

We 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

This 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

Minimum 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

The 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

An 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.
Anticenters and antimedians of a network
Authors: Minieka Edward
Published: May 2007

This paper presents methods for the optimal location of facilities in a network when the traditional criteria of minimizing distance is replaced by maximization.
A survey of heuristics for the weighted matching problem
Authors: Avis David
Published: May 2007

This 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

Let 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

In 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

We 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

Let 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

In 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.
Euclidean shortest paths in the presence of rectilinear barriers
Authors: Lee D. T. , Preparata F. P.
Published: May 2007

In this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an Ω(n2) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n‐vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest‐path tree from the source to all the vertices of the obstacles and to the destination.
Routing with time windows by column generation
Authors: Desrosiers Jacques , Soumis François , Desrochers Martin
Published: May 2007

Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost, and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required, together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to the number of vehicles, and the travel costs between trips, are minimized. The problem is a generalization of the m‐traveling salesman problem. We use column generation on a set partitioning problem solved by simplex and branch‐and‐bound; columns are generated by a shortest path algorithm with time windows on the nodes. Numerical results for several school bus transportation problems with up to 151 trips are discussed.
Minimum cuts, modular functions, and matroid polyhedra
Authors: Cunningham William H.
Published: May 2007

The minimum cut problem is a well‐solved special case of submodular function minimization. We show that it is in fact equivalent to minimizing a modular function over a ring family. One‐half of this equivalence follows from classical work of Rhys and Picard. We give a number of applications to testing membership in special kinds of matroid polyhedra.
An efficiently solvable case of the minimum weight equivalent subgraph problem
Authors: Richey M. B. , Parker R. Gary , Rardin R. L.
Published: May 2007

Given a directed graph G(𝓋,𝒶), the problem of finding a minimum cardinality subset υ ⊆ 𝒶 such that the subgraph, G(𝓋,𝒶), preserves the reachability properties of G(𝓋,𝒶) is well known to be difficult. In this article, we consider a generalization which seeks a minimum weight subset υ satisfying the stated conditions where the weights of arcs in 𝒶 are assigned arbitrary integer values. A polynomial‐time algorithm is given for the case where the underlying, undirected graph is series‐parallel. Naturally, the stated algorithm subsumes the cardinality case on such graphs as well.
Locating a facility on a congested network with random lengths
Authors: Berman Oded
Published: May 2007

This article deals with a location problem on networks that are characterized by two types of uncertainties. The first type of uncertainties relates to the travel times on the network which are not deterministic but usually undergo random changes. The second type of uncertainties relates to the demands for service which may occur at different places in the network and at random times. The consequence of the second type of uncertainties is a system which may undergo periods of intense activity as well as other periods of relative inactivity. Previous research has dealt with each one of the two types of uncertainties separately. The objective of the paper is to locate a facility that garages a single server so as to minimize the expected cost of response. Results are obtained for two models. In one model demands that occur while the server is busy are rejected whereas in the other model queueing is allowed. The special case when the network is a tree is also considered.
An algorithm for the steiner problem in the euclidean plane
Authors: Winter Pawel
Published: May 2007

An algorithm for the exact solution of the Steiner problem in the Euclidean plane is presented. Compared with earlier algorithms, it generates full topologies in a different manner whereby the number of computations is substantially reduced. Furthermore, a large number of full Steiner trees which do not belong to the Steiner minimal tree is identified and discarded by new and efficient tests. The algorithm appears to be considerably faster than any other existing algorithm.
The Gilbert and Pollak conjecture—a generalization
Authors: Trietsch Dan , Handler Gabriel Y.
Published: May 2007

Gilbert and Pollak conjectured that the length of the minimal Steiner tree (MST) is at least \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt {3/4} $\end{document} that of the minimal spanning tree. In a subsequent paper, Gilbert generalized the Steiner tree problem by adding flow dependent weights to the arcs. We refer to the generalized problem as the Minimal Gilbert Network Problem, and to its optimal solution as the Minimal Gilbert Network (MGN). The purpose of this article is to generalize Gilbert and Pollak's conjecture to the ratio between the MGN and the regular minimal network (where extra nodes are not allowed). We prove that when the regular minimal network connects three nodes, the highest improvement possible, by adding exactly one extra point, is (2 − \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt 3 $\end{document})/2, and that this maximal improvement can be achieved only for the symmetric case, namely, where the three nodes are the vertices of an equilateral triangle and the weights of the three arcs are equal. As this is actually a Steiner tree case, we believe that the generalized and the original conjectures are equivalent, i.e., if this generalized conjecture will ever be disproved, the counterexample (or at least one of the possible counterexamples) would also disprove the original conjecture. Another result we present is a proof of the existence of the Gilbert generalized Steiner construction.
Probabilistic partitioning algorithms for the rectilinear steiner problem
Authors: Komlós János , Shing M. T.
Published: May 2007

Based on the probabilistic approach introduced by Karp [14], we present two partitioning algorithms for the approximate solution of large instances of the rectilinear Steiner problem in the plane. The algorithms subdivide a set of given points into small groups, construct a minimum rectilinear Steiner tree for each small group, and then patch the subtrees together to form a near‐optimum rectilinear Steiner tree for the given points. Suppose there are n given points, uniformly distributed over the unit square [0,1] × [0,1] and spanned by a minimum rectilinear Steiner tree To. Then for any given integer t > 0, the first algorithm runs in O(f(t)n + n log n) time and produces a rectilinear Steiner tree T1 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_1 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞, while the second algorithm has an expected running time of O(g(t)n) and it also produces a rectilinear Steiner tree T2 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_2 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞.
Reducing complexities of the distributed max‐flow and breadth‐first‐search algorithms by means of network synchronization
Authors: Awerbuch Baruch
Published: May 2007

This article presents new simple distributed Maximum Flow and Breadth‐First Search algorithms for an asynchronous communication network. Our algorithms improve the best known algorithms both in the communication and time complexities. The basic idea is first to “synchronize” the network and then to apply synchronous algorithms which use efficiently the parallelism of the model.
The average height of the d‐th highest leaf of a planted plane tree
Authors: Prodinger Helmut
Published: May 2007

It is proved that the dth highest leaf, where all planted plane trees with n nodes are assumed to be equally likely, has an average height \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt {\pi n} ‐ \frac{1}{2} ‐ \frac{2}{3}\sum\nolimits_{s = 1}^{d ‐ 1} {\left({2/9} \right)^s \left({\begin{array}{*{20}c} {2s + 1} \\ s \\ \end{array}} \right)} + O\left({n^{‐ 1/2 + \varepsilon}} \right) $\end{document} for all ϵ > 0 and n → ∞. This solves a problem left open in one of our previous papers.
Shout echo selection in distributed files
Authors: Rotem Doron , Santoro Nicola , Sidney Jeffrey B.
Published: May 2007

An algorithm for selecting the kth smallest element of a distributed file using shout‐echo communication primitives is presented. It is shown that, for large values of k (e. g., the median), the proposed algorithm improves the existing upperbound.
Configuration of physical distribution networks
Authors: Daganzo Carlos F. , Newell Gordon F.
Published: May 2007

Distribution problems, including vehicle routing and warehouse location problems, are usually formulated by considering a finite number of possible locations for the customers, the warehouses, and vehicle stops. The question of selecting which of these points are actually used (and how) is a mixed‐integer programming problem which is difficult to solve. Thus, such a discrete formulation results in a problem that has to be solved heuristically; it also entails a large data preparation effort each time a solution has to be developed in response to changing world conditions. The continuous approach used in this paper attempts to circumvent some of these drawbacks. We consider one source and its customers in a service area; customer locations are modeled by a density surface over the service area. With this information, and data about the cost of inventory and transportation, we can determine the number of transhipment points, and the frequency and routing of all the distribution vehicles. An example is given. The continuous approach does not yield a solution. It gives design guidelines, which ensure near minimum total cost. These design guidelines are based on general properties of optimal solutions (discussed at the beginning of the paper) and on the specific characteristics of the case at hand. Implementation of the guidelines to obtain a feasible configuration requires human intervention. While the continuous method involves approximations (the real world is discrete and considerably more complicated than in our model), it yields insight into the structure of logistic systems. This insight should not only help in the design process; it may well also lead to improved heuristic solution methods for discrete formulations. Hybrid methods may eventually emerge.
Iterative algorithms for generating minimal cutsets in directed graphs
Authors: Shier D. R. , Whited D. E.
Published: May 2007

Several approaches for evaluating network reliability require the generation of all minimal cutsets in a directed graph. A general iterative algorithm, based on an underlying algebraic structure, is proposed for generating all minimal s−j cutsets simultancously for all vertices j in such a graph. In order to implement this algorithm in an efficient manner and to exploit sparsity present in the graph, a number of computational simplifications are developed, leading to improved performance of the algorithm. Empirical results show that the choice of certain data structures can have a profound effect on the computational effort required.
On the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
Authors: Solomon Marius M.
Published: May 2007

We consider the vehicle routing and scheduling problem with time window constraints. Analytical results concerning the behavior of approximation methods for this problem class are derived through worst‐case analysis. For a variety of heuristics, it is shown that their worst‐case behavior on n customer problems is at least order of n for minimizing the number of vehicles used, the total distance traveled, and the total schedule time.
Optimally reliable graphs for both edge and vertex failures
Authors: Evans Trefor , Smith Derek
Published: May 2007

The problem of describing graphs representing a communication network which are optimally reliable has been studied both for the case of vertex failures and for the case of edge failures. We give a combinatorial definition in each case and show that under certain conditions the first definition implies the second. We use this result to investigate the existence of graphs which in some sense are optimally reliable with respect to both vertex and edge failures.
Network decomposition for the optimization of connection structures
Authors: Iwainsky Alfred , Canuto Enrico , Taraszow Oleg , Villa Agostino
Published: May 2007

In many practical situations, connection structures have to be laid out in an environment with a strong inner structure. This article presents a new general mathematical formulation of cor responding design problems in which the layout possibilities are represented by a network. Because in practice such networks are often very large and sparse, there is great interest in the utilization of decomposition techniques for the optimization of connection structures. New decomposition methods for the determination of optimal paths without interference (independent decom position), of k node‐disjoint paths with minimal total costs and of optimal Steiner trees are presented. The new methods are compared with other techniques under different aspects of practical importance.
A random network model of message transmission
Authors: Pullen Karen W.
Published: May 2007

A model for message transmission through a network with unreliable nodes and links is presented; the assumptions are that nodes and links operate independently with probabilities α and β respectively. The following performance measures are derived: the probability of reaching k nodes by transmission m, the probability an arbitrary operable node is reached on the mth transmission, and the probability that d transmissions are required to reach all operable nodes. The algorithms are illustrated with a five‐node example network; some performance measures are shown graphically for a range of parameter values. This work was sponsored by the Electronic Systems Division of the United States Air Force Systems Command.
On multiple steiner subgraph problems
Authors: Richey M. B. , Parker R. Gary
Published: May 2007

Recently, much attention has been given to the solvability of (otherwise intractable) combinatorial optimization problems when instances are confined to series‐parallel graphs. Substantially less is known, however, regarding those that remain hard on these particularly sparse structures. While a few ad hoc cases have been shown to be difficult, little appears to be known in terms of more generic settings. In this paper, we contend with this state of affairs by establishing that a class of Steiner subgraph‐like problems are NP‐complete on series‐parallel graphs while remaining easy (even trivial) on trees.
The node‐weighted steiner tree problem
Authors: Segev Arie
Published: May 2007

The general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.