bluuebunny/crossref_metadata_2025 huggingface dataset:
A probabilistic model for the analysis of the routing process for circuits
Authors: Agrawal P. , Breuer M. A.
Published: May 2007

A probabilistic model is developed for studying the problem of routing printed circuits. The model, which uses the density of blockages on the carrier as a parameter, is based on the path‐searching mechanism of Lee's algorithm. Lee's algorithm is used in our analysis because it belongs to a class of pathfinding procedures which guarantee finding a path between two given points if one exists. It is shown that the routing probability, RM(d), is bounded above by PM(d), where PM(d) is the probability of existence of an arbitrary path of ideal Manhattan distance d from a given source point. Analytical computation shows that PM(d) is practically one until a density of about 35%. After this it sharply reduces, reaching a negligible value at a density of 43% for all but very small values of d. Some experiments related to the verification of the model are described. These experimental results show good agreement with the theoretically derived probabilities.
An algorithm to solve the m × n assignment problem in expected time O(mn log n)
Authors: Karp Richard M.
Published: May 2007

We give an algorithm to solve the m‐source, n‐destination assignment problem in expected time O(mn log n) under the assumption that the edge costs are independent random variables and the costs of the edges incident with any given source are identically distributed. The algorithm achieves its efficiency through an unusual application of priority queues.
Efficient special case algorithms for the n‐line planar traveling salesman problem
Authors: Cutler M.
Published: May 2007

The traveling salesman problem, path, or cycle is NP‐complete. All known exact solutions to this problem are exponential. In the N‐line planar traveling salesman problem the points are on N lines in the plane. In this paper, simple and efficient low‐degree polynomial solutions are given to some N‐line (N = 2, 3) planar traveling salesman problems using dynamic programming. Such problems arise in practical applications, for example, connecting nets in printed circuits.
Conditional centers and medians of a graph
Authors: Minieka Edward
Published: May 2007

Previous treatments of location problems on a graph have been confined to the optimum location of a single facility or the simultaneous optimum location of multiple facilities. This paper addresses the problem of optimally locating a facility on a graph when one or more other facilities have already been located in the graph. This paper shows that previous solution techniques can be reused if the distances in the graph are judiciously redefined.
A recursive algorithm for finding reliability measures related to the connection of nodes in a graph
Authors: Buzacott J. A.
Published: May 2007

A recursive algorithm is developed for finding the probability that not all nodes are connected in a graph with arcs that can fail. The number of multiplications required by the algorithm when applied to a complete graph on n nodes is shown to be of order 3n‐1, substantially less than other published algorithms. Further, it is shown that the algorithm enables other reliability measures related to the connection of nodes in a graph to be determined with minimal extra multiplications. The algorithm can also form the basis of methods for calculating the reliability measures of graphs with unreliable nodes and unreliable arcs. The complexity is then at worst 4n and, in most cases, of order 3n.
Localizing 2‐medians on probabilistic and deterministic tree networks
Authors: Mirchandani Pitu B. , Oudjit Aissa
Published: May 2007

Locating a single facility (the 1‐median problem) on a deterministic tree network is very efficiently solved by Goldman's algorithm. This paper explores the possibility of efficiently solving the 2‐median problem for both deterministic and probabilistic tree networks. Interesting properties (Theorems 1–4) are derived that relate the location of 1‐median to the location of pairs of 2‐medians. Two simple algorithms, the “Improved Link‐Deletion” algorithm for the deterministic case and the “Selective Enumeration” algorithm for the probabilistic case, are presented which somewhat improve existing methods to determine 2‐medians on tree networks.
Investment in stochastic minimum cost generalized multicommodity networks with application to coal transport
Authors: Wollmer Richard D.
Published: May 2007

In a generalized multicommodity network, certain resources are in limited supply. The total consumption of any resource is a linear combination of the individual arc flows. In this problem the supply of any resource is a non‐negative random variable which may be increased by an investment. The objective is to invest in resources in a way that minimizes total expected cost. This problem is formulated as a two stage linear program under uncertainty. The first stage variables are the amounts that are to be invested in each resource. The values of the first stage variables are determined before the actual values of the random variables become known. The second stage variables correspond to the amount of flow on each arc of each commodity. The values of the second stage variables are determined after the actual values of the random variables are known. The solution techniques given exploit the network structure in both the first and second stage.
The complexity of designing a network with minimum diameter
Authors: Plesnik J.
Published: May 2007

Given a graph G with edge lengths and costs, we wish to find a subgraph F of G which connects up all the original vertices and minimizes the maximum distance in F, subject to a budget constraint on the sum of the edge costs. In this note we establish NP‐hardness for the design problem, even for the simple case where G is a planar graph with maximum degree 3 and the budget restricts the choice to spanning trees. Moreover, the problem of finding a near optimal subgraph F is also NP‐hard.
Set partitioning based heuristics for interactive routing
Authors: Cullen Frank H. , Jarvis John J. , Ratliff H. Donald
Published: May 2007

The set partitioning model is used as the basis for an interactive approach for solving a broad class of routing problems. A pricing mechanism is developed which can be used with a variety of methods in generating improving solutions. A version of the approach for delivery problems has been implemented via a colorgraphics display. The human aided optimization procedure was tested on the standard 50‐point, 75‐point, and 100‐point test problems of Eilon, Watson‐Gandy, and Christofides [6]. In the case of the first two test problems, the procedure was able to generate the best known solutions. In the 100‐point problem, a better solution was generated than the current best known solution.
The k‐nucleus of a graph
Authors: Slater Peter J.
Published: May 2007

In an earlier paper the measures of centrality in a graph G demonstrated by the center and centroid were unified and generalized, resulting in the definition of the h‐centrum of G and denoted C(G;h) for 1 ≤ h ≤ |V(G)|. When dealing with the h‐centrum one sums the distances from a given vertex u to each of the h vertices farthest from it. Here another way of generalizing the concepts of center and centroid is examined, and the k‐nucleus is defined for G and denoted θk(G). When dealing with the k‐nucleus one sums the distances from a given vertex u to the balls of radius k around each of the other vertices. The centroid of G is θo(G), and the center of G is θr(G), where r is the radius of G. Some relationships between the h‐centra and the k‐nuclei are presented.
Capacitated arc routing problems
Authors: Golden Bruce L. , Wong Richard T.
Published: May 2007

A capacitated node routing problem, known as the vehicle routing or dispatch problem, has been the focus of much research attention. On the other hand, capacitated arc routing problems have been comparatively neglected. Both classes of problems are extremely rich in theory and applications. Our intent in this paper is to define a capacitated arc routing problem, to provide mathematical programming formulations, to perform a computational complexity analysis, and to present an approximate solution strategy for this class of problems. In addition, we identify several related routing problems and develop tight lower bounds on the optimal solution.
A note on the problem of updating shortest paths
Authors: Fujishige Satoru
Published: May 2007

The problem of updating shortest paths from all the vertices to a set of vertices when the length function is decreased was considered by S. Goto and A. Sangiovanni‐Vincentelli and a solution algorithm was presented based on the LU‐factorization of the measure matrix and a matrix inversion formula. The present paper shows that the problem can be solved by means of the Dijkstra method in a running time of the same order as Goto and Sangiovanni‐Vincentelli's algorithm, assuming a smaller amount of initial data than theirs, i.e., we do not need the LU‐factorization of the measure matrix.
A dual simplex algorithm for finding all shortest paths
Authors: Florian M. , Nguyen S. , Pallottino S.
Published: May 2007

We present an adaptation of the dual simplex algorithm, for computing all shortest paths on a network. Given a shortest path arborescence rooted at node r, the change of root to a new origin s, renders the arborescence rooted at r dual feasible and primal infeasible for the new problem. The adaptation of the dual simplex algorithm to compute the shortest paths from node s results in an algorithm which has the flavor of a label‐setting method. It generally does not require the examination of all the nodes of the network. We report some computational results with the method which indicate that it is at least as efficient as successive applications of a label‐setting or a label‐correcting shortest path algorithm.
A shortest augmenting path method for solving minimal perfect matching problems
Authors: Derigs Ulrich
Published: May 2007

An efficient procedure for solving minimum weight perfect matching problems is presented. Starting from the empty matching the optimal matching is constructed by successively augmenting along shortest augmenting paths. Such paths can be determined via a special labeling technique. The algorithm is motivated by purely combinatorially natured optimality criteria using the concept of admissible transformations of the cost coefficients. We report on some experience with computer implementations of two different versions of this method and an implementation of Edmonds' BLOSSOM‐algorithm which makes use of Lawler's labeling technique. Though all three methods are comparable with respect to computational complexity the results indicate that the shortest augmenting path method is superior with respect to running time and that even larger problems may be solved in a reasonable amount of time.
The general multimodal network equilibrium problem with elastic demand
Authors: Dafermos Stella
Published: May 2007

In this article, we consider the general multimodal traffic equilibrium model with elastic demands. The link travel costs may depend upon the entire load pattern and the travel demands associated with each origin‐destination pair and mode may depend upon travel costs associated with every origin‐destination pair and every mode of transportation. For this model, we define the concepts of user‐optimality and equilibrium. We establish, by means of a constructive proof motivated by the theory of variational inequalities, the existence of a unique equilibrium under appropriate monotonicity conditions. We then show that the existence proof induces an algorithm for the computation of equilibrium traffic patterns. The algorithm proceeds by iteration, each step of which amounts to computing the equilibrium pattern for a single modal linear traffic equilibrium problem with elastic demands. We derive estimates for the speed of convergence.
Generalizations of planar graphs
Authors: Erickson Ranel E.
Published: May 2007

Two new generalizations of planar graphs, called quasiplanar and pseudoplanar graphs, are introduced and discussed. It is shown that planar graphs are quasiplanar and these in turn are pseudoplanar. Conversely, a pseudoplanar graph that contains with each arc its reverse arc is quasiplanar. A Kuratowski‐type characterization of quasiplanar graphs is given; in it the excluded subgraphs differ from Kuratowski's only by the addition of an edge in the bipartite graph.
Minimum width 2‐layer layout of a multichanneled system
Authors: Cutler M. , Riesel Z.
Published: May 2007

A special layout problem is considered. It is shown that the problem is NP‐complete. For a system with a small number of channels k, a polynomial algorithm is given, finding a layout with a width differing from the minimum by at most k + 1. For a system with a large number of channels k, an approximation algorithm is presented. Given an ϵ > 0 this algorithm finds a layout with a width differing from the minimum by at most ϵZ + k + 1, where Z is a lower bound on the width. The complexity of this algorithm depends on ϵ.
Double‐row planar routing and permutation layout
Authors: Tsukiyama Shuji , Kuh Ernest S.
Published: May 2007

Problems on layout for ICs (integrated circuits) and PCBs (printed circuit boards) are usually solved by heuristic approaches because they are complex. This article considers a special problem of double‐row planar routing. The problem represents a generalization of the permutation layout problem to which estimation of bounds and some algorithms have been proposed recently. Our approach is based on the interval graphical representation introduced in the single‐row single‐layer PCB problem. The objective function for minimization is the breadth of the realization, i.e., the total number of vertical tracks required to realize a given net list specified in terms of terminals on two parallel rows. The problem is shown to be intractable in the sense of NP‐completeness; however, a polynomial‐time heuristic algorithm is proposed. An upper bound for the breadth for an initial solution is given. Iterative improvement is next used. The algorithm has been programmed in FORTRAN and ran on the VAX 11/780 computer.
An algorithm for the steiner problem in graphs
Authors: Shore M. L. , Foulds L. R. , Gibbons P. B.
Published: May 2007

The Steiner problem in graphs is concerned with finding a set of edges with minimum total weight which connects a given subset of points in a weighted graph. A branch and bound algorithm for solving this problem is presented together with an interesting application to a problem in molecular evolution. Computational experience gained in using the algorithm compares favorably, for certain classes of graphs, with that of existing methods.
Topological design of centralized computer networks—formulations and algorithms
Authors: Gavish Bezalel
Published: May 2007

In recent years we have evidenced an extensive effort in the development of computer communication networks. One of the important aspects of the network design process is the solution of the topological design questions involved in establishing a communication network. In this article, formulations are presented for a variety of centralized network design problems such as the minimal spanning tree problem, capacitated and degree constrained minimal spanning tree problems, The Telpak problem, and, heterogeneous network design problems. The applicability of these formulations to algorithmic development is demonstrated by developing an efficient algorithm for solving the degree constrained minimal spanning tree problem. Computational results are reported for 630 test problems. A Bender's decomposition procedure is developed and tested for the capacitated minimal spanning tree problem with less favorable results.
Algorithmic approaches to preselective strategies for stochastic scheduling problems
Authors: Lgelmund G. , Radermacher F. J.
Published: May 2007

This article deals with a fairly general model of stochastic scheduling problems, for which the class of preselective strategies was recently introduced. This class proved to be of considerable importance, one of the reasons being that it forms, in a certain sense, the greatest class of strategies leading to a certain stability behavior. Furthermore, this uncountably infinite class is essentially determined by a finite number of well‐behaving <‐minimal strategies, viz. special so‐called MES ors‐induced strategies. This fact is used in the present article to show how MES strategies can be treated algo‐rithmically. The approach used is an implicit enumeration scheme, based on a branch‐and‐bound method; this is illustrated in a fair number of examples.
Network reliability and the factoring theorem
Authors: Satyanarayana A. , Chang Mark K.
Published: May 2007

In network reliability analysis, an important problem is to determine the probability that a specified subset of vertices in an undirected graph is connected. It is well known that, by using Moskowitz's factoring theorem, the reliability of a graph can be expressed in terms of the reliabilities of a graph with one fewer vertex and another with one fewer edge. The theorem can be applied recursively on the reduced graphs. The computations involved in this recursion can be represented by a binary structure such that its leaves correspond to reduced graphs whose reliabilities can be readily evaluated. In general, as the recursion progresses, series and parallel edges are created which can be reduced by using series and parallel rules of reliability assuming edges fail independently of each other. The computational complexity is a function of the number of leaves in the binary structure, and for a given graph, an optimal binary structure is the one with minimal number of leaves. In this article, a combinatorial invariant of a graph, called the domination, is established. Several important properties of the domination with regard to the topology of the graph are investigated. It is shown that for a given graph, the number of leaves in the optimal binary structure is equal to the domination of the graph and recursive application of the factoring theorem yields an optimal structure if and only if at each step the reduced graphs generated have nonzero dominations. Finally, an algorithm is presented that guarantees optimal binary structure generation and therefore an efficient implementation of the factoring theorem to compute the network reliability.
A note on Arc tolerances in sparse shortest‐path and network flow problems
Authors: Gusfield Dan
Published: May 2007

In the article “Arc Tolerances in Shortest‐Path and Network Flow Problems” by D. R. Shier and C. Witzgall, several methods were described to compute, relative to a given tree T, the “arc tolerance” of each arc in a graph G of n nodes and A arcs. One method, the “dead‐end retraction” method was shown to take O(n2) time and O(n2) space, and another method, the “cycle‐tracing” method was shown to take O(nA) time but only O(A) space. For the important case of large sparse graphs, these methods either require excessive time, or excessive space. In this note implementations of both of the above methods are described which require O(A) space and O(A) log n) time. In the cycle‐tracing method this is a strict improvement even for the dense case.
A network decomposition/aggregation procedure for a class of multicommodity transportation problems
Authors: Evans James R.
Published: May 2007

An effective method of solving a practical class of multicommodity transportation problems is presented. The heuristic procedure combines theoretical results concerning multicommodity network structures and recent results on aggregation theory. Computational implementation has shown that problems with thousands of variables can be solved to within a few percent of optimality in a matter of seconds. Only widely available network codes are required to implement the procedure, thus making it attractive for smaller computers.
A recursive algorithm for directed‐graph reliability
Authors: Buzacott J. A.
Published: May 2007

It is shown that the recursive algorithm for determining the reliability measures relating to the connection of nodes in an undirected graph can also be applied to directed graphs with no increase in the computational requirements. The resulting algorithm is compared with a number of other directed‐graph reliability algorithms and is shown to require, on complete graphs, significantly fewer multiplications than any existing algorithm.
Circuit partitioning with size and connection constraints
Authors: Perl Yehoshua , Snir Marc
Published: May 2007

The problem of partitioning a circuit into subcomponents with constraints on the size of each subcomponent and the number of external connections is examined. While this problem is shown to be NP‐complete even for very restricted cases, a pseudo‐polynomial dynamic programming algorithm is given for the case where the circuit has a tree structure.
Stochastic bottleneck spanning tree problem
Authors: Ishii Hiroaki , Nishida Toshio
Published: May 2007

This paper considers a stochastic version of bottleneck spanning tree problem in which edge costs are random variables. The problem is to find an optimal spanning tree under the chance constraint with respect to bottleneck (maximum cost) edge of spanning tree. The problem is first transformed into a deterministic equivalent problem. Then its subproblem is introduced and a close relation between these problems is clarified. Finally, based on the relation, an algorithm which finds an optimal spanning tree of the original problem in a polynomial order of its problem size is proposed.
The perfectly matchable subgraph polytope of a bipartite graph
Authors: Balas Egon , Pulleyblank William
Published: May 2007

The following type of problem arises in practice: in a node‐weighted graph G, find a minimum‐weight node set that satisfies certain conditions and, in addition, induces a perfectly matchable subgraph of G. This has led us to study the convex hull of incidence vectors of node sets that induce perfectly matchable subgraphs of a graph G, which we call the perfectly matchable subgraph polytope of G. For the case when G is bipartite, we give a linear characterization of this polytope, i.e., specify a system of linear inequalities whose basic solutions are the incidence vectors of perfectly matchable node sets of G. We derive this result by three different approaches, using linear programming duality, projection, and lattice polyhedra, respectively. The projection approach is used here for the first time as a proof method in polyhedral combinatorics, and seems to have many similar applications. Finally, we completely characterize the facets of our polytope; i.e., we separate the essential inequalities of our linear defining system from the redundant ones.
Dynamic matchings and quasidynamic fractional matchings. I
Authors: Orlin James B.
Published: May 2007

This paper presents and solves in polynomial time the dynamic matching problem, an integer programming problem which involves matchings in a time‐expanded infinite network. The initial model is a finite directed graph G = (V, E) in which each edge has an associated real‐valued weight and an integral distance. We wish to “match” vertices over an infinite horizon, and we permit vertex i in period p to be matched to vertex j in period r if and only if there is an edge e = (i, j) of E with distance r‐p or else an edge e = (j, i) of E with distance p‐r. Equivalently, we construct a “dynamic graph” in which there is an edge incident to vertex i‐p and to vertex j‐r in the above cases. The weight of this matched edge in the dynamic (time‐expanded) graph is the weight of e. The dynamic matching problem is to determine a matching M in the dynamic graph such that M has a maximum long‐run average weight per period. We show that the infinite horizon dynamic matching problem is linearly transformable to the finite horizon Q‐matching problem, which is shown to be solvable in polynomial time in Part II of this paper.
An algorithm for construction of a k‐connected graph with minimum number of edges and quasiminimal diameter
Authors: Schumacher Ulrich
Published: May 2007

Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node‐disjoint paths between any two nodes. The generated graphs will have a minimum number of edges and a diameter which is twice as large as the theoretical minimum. The algorithm is useful for the construction of large networks because it has a time complexity of O(n2).
The period routing problem
Authors: Christofides N. , Beasley J. E.
Published: May 2007

In this paper we present heuristic algorithms for the period vehicle routing problem, the problem of designing vehicle routes to meet required service levels for customers and minimize distribution costs over a given several‐day period of time. These heuristic algorithms are based on an initial choice of customer delivery days which meet the service level requirements, followed by an interchange procedure in an attempt to minimize distribution costs. The heuristic algorithms represent distribution costs by replacing the vehicle routing problem for each day of the period by (i) a median problem and (ii) a traveling salesman problem. Computational results and comparisons are given for the algorithms, based on test problems derived from the literature with up to 126 customers. The largest of these problems is the one given and solved by Russell and Igo. The solution obtained for this problem by the heuristic algorithms shows an improvement of 13% over the previous best solution.
Shortest‐path algorithms: Taxonomy and annotation
Authors: Deo Narsingh , Pang Chi‐Yin
Published: May 2007

We have evolved a classification scheme to characterize algorithms for solving shortestpath problems. The algorithms are classified according to (A) the problem type, i.e., the question being asked about the given network; (B) the input type, i.e., the salient features of the given network which impact on the design of the algorithm and selection of data structures; and (C) the type of underlying technique employed to solve the problem. An annotated bibliography of 79 selected references on shortest‐path algorithms is included. We have also provided a more complete listing of 222 references carefully culled out of a larger body of literature on shortest‐path algorithms through the year 1979.
An extremal problem on the connectivity of graphs
Authors: He Qi‐Mei
Published: May 2007

We solve in this paper a problem proposed by Bi‐weng Zhu at the First Combinatorics and Graph Theory Conference of China. For the minimum degree δ, connectivity k, and line‐connectivity λ of a (p,q) graph, p,q fixed, the maximum values of δ ‐ k, δ ‐ λ, and λ ‐ k are given as well as extremal graphs for which these upper bounds are realized.
Bounds on expected performance of networks with links subject to failure
Authors: Carey Malachy , Hendrickson Chris
Published: May 2007

Upper and lower bounds on the expected maximum flows and benefits in capacitated networks with links subject to random failure are presented. Such bounds are of interest both because of the high or prohibitive cost of computing the exact expected values, and because the exact values will depend on the extent to which management avails itself of the opportunities for rerouting of flows in response to link failures. Algorithms for computing these bounds are discussed. These algorithms are sufficiently efficient to be applied to large networks having numerous possible failure states. An application to water‐network seismic risk analysis is described.
Network reliability and acyclic orientations
Authors: Johnson R.
Published: May 2007

Let G = (V, E) be an undirected graph with V = n perfectly reliable vertices and E = m edges that work with probability pe and fail with probability qe for all e /in E. The network reliability problem considered here is to calculate RK[G] = Prob [there exists a path of working edges between every pair of a set K of k vertices]. Backtrack algorithms for this problem are presented. The complexity of these algorithms is discussed when applied to the all‐terminal network reliability problem where K = V. Strategies are presented which minimize the size of the search structures generated. The main theorems state that when these strategies are used, the size of the search structures may be measured by counting spanning trees or acyclic orientations.
The even‐path problem for graphs and digraphs
Authors: Lapaugh Andrea S. , Papadimitriou Christos H.
Published: May 2007

We give a simple linear‐time algorithm for finding even‐length simple paths between two specified nodes of a given graph. We show that the same problem for directed graphs is NP‐complete.
Note on independence of arcs in antiparallel for network flow problems
Authors: Hagstrom Jane Nichols
Published: May 2007

Given a transportation flow network with two arcs in antiparallel, if the capacities of all other arcs are fixed and the demands at sinks are fixed, at least one of the two arcs will be irrelevant to the problem of flow feasibility. As a consequence, in a stochastic setting, two arcs in antiparallel whose capacities are independent of other network capacities and demands may be treated as having independent probability distributions regardless of their actual correlation.
A routing procedure for an IC module with many pins—a solution to a circular permutation layout problem
Authors: Ozawa Takao
Published: May 2007

This article considers routing for an IC module with many pins which is mounted on a board. Routing for such an IC module must be planar. It is also constrained by the order of pins and the congestion between pins (the number of wires passing between adjacent pins) of the module. The routing procedure presented in this paper is recursive: First, routing to a particular pin passing between two adjacent pins is tried in order to fix the relative position of the module on the board. If this can be done, the set of pins is divided into two subsets. Then routing to a pin or two in each of the subsets is tried. If this is successful, routing to a pin or two is tried again in each of the resulting smaller subsets. This process is repeated, if possible, until the entire routing for the module is completed. If no legal routing is found in the recursion process, the procedure goes back to the beginning of the recursion and tries a new initial routing until all the possible initial routings are exhausted. The time complexity and the space complexity of the procedure are O(l2) and O(l), respectively, in the worst case where l is the number of pins of the module. The procedure can be regarded as a solution to a circular permutation layout problem.
Rectangular duals of planar graphs
Authors: Koźmiński Krzysztof , Kinnen Edwin
Published: May 2007

Let one face of a cube be dissected into rectangles, no 4 of which meet at a single point. The dual graph of this configuration is a 4‐connected triangulated plane graph. This paper shows that any 4‐connected plane triangulation with at least 6 vertices and at least one vertex of degree 4 is dual to a cube with one face dissected into rectangles. The proof of this result contains an implicit algorithm for obtaining such a dissection. The paper also discusses a related problem: Given a graph G with all faces triangular except the outer face, does there exist a dissection of a rectangle into rectangles for which G describes the adjacency relations among the rectangles?
The continuous m‐center problem on a network
Authors: Handler Gabriel Y. , Rozman Margalit
Published: May 2007

In the continuous m‐center problem on a network, m‐centers are to be located along the arcs of the network so as to minimize the maximum (shortest) distance from any point on the network to a nearest center. The typical application scenario is to the location of emergency facilities in a transportation network. In this article, we propose a solution procedure for this hitherto unsolved problem. The procedure is a relaxation algorithm which may be viewed as a column and row generating procedure for the infinite size covering problems needed to solve the problem. The optimum‐seeking procedure is expected to be practical for large‐scale networks.
The search value of a network
Authors: Alpern Steve , Asic Miroslav
Published: May 2007

Let Q be a connected network with a distinguished (starting) point q0, whose are lengths sum to one. We associate with Q a “search value” V(Q) representing the expected time needed for a searcher, starting at q0 and moving at unit speed, to find a moving hider. We assume neither sees the other until they meet. We demonstrate that the “figure‐eight” network, consisting of two equal loops joined at a central starting point, has a search value not exceeding 15/16. This contradicts a conjecture of Gal that the search value of any network is at least 1. In the other direction, we show that V(Q) ≦ 6kD for a network with k edges and diameter D.
On the relationship between Nash—Cournot and Wardrop equilibria
Authors: Haurie A. , Marcotte P.
Published: May 2007

A noncooperative game is formulated on a transportation network with congestion. The players are associated with origin‐destination pairs, and are facing demand functions at their respective destination nodes. A Nash‐Cournot equilibrium is defined and conditions for existence and uniqueness of this solution are provided. The asymptotic behavior of the Nash‐Cournot equilibrium is then shown to yield (under appropriate assumptions) a total flow vector corresponding to a Wardrop equilibrium.
Block‐vertex duality and the one‐median problem
Authors: Chen M.‐L. , Francis R. L. , Lawrence J. F. , Lowe T. J. , Tufekci S.
Published: May 2007

The w‐centroid problem, denoted by (C), is an optimization problem which has been shown by Kariv and Hakimi to be equivalent, on a tree graph, to the 1‐median location problem, denoted by (M). For a general (weighted) connected graph G we develop a duality between (C) (which is defined on G) and a block optimization problem, denoted by (B), and defined over the blocks of G. A block is a maximal nonseparable subgraph. We analyze (B) and (C) by means of two problems equivalent to (B) and (C) respectively, but defined on a blocking graph G which is always a tree. We give an O(∣V∣) algorithm to solve the two problems on G, and we characterize the solutions. We also show that the solution to a 1‐median problem defined on G either solves (M) on the original graph G or localizes the search for a solution to (M) to the vertices of a single block. We introduce an extended version of Goldman's algorithm which (in linear time) either solves (M) on G, or finds the single block of G which contains all solutions to (M).
Solving large‐scale matching problems efficiently: A new primal matching approach
Authors: Derigs Ulrich
Published: May 2007

In this article we introduce a new approach to the weighted matching problem. It is designed specifically for problems defined on large dense graphs. It is a two‐phase approach that first solves a matching problem on a sparse subgraph and then considers the remaining edges in a pricing out/reoptimization phase. Computational experience is reported which documents the efficiency of this algorithm.
An exact algorithm for the asymmetrical capacitated vehicle routing problem
Authors: Laporte Gilbert , Mercure Hélène , Nobert Yves
Published: May 2007

The aim of this article is to develop an exact algorithm for the asymmetrical capacitated vehicle routing problem, i. e., the multiple traveling salesman problem subject to capacity restrictions. The problem is solved by means of a branch and bound tree in which subproblems are modified assignment problems subject to some restrictions. Two branching rules and three partitioning rules are examined. Computational results for problems involving up to 260 nodes (cities) are reported.
Underlying properties of oriented graphs
Authors: McKee T. A.
Published: May 2007

A formal analysis is made of the interconnection between oriented graphs and their underlying graphs, illustrating more general situations such as underlying graphs of networks. A natural notion of an “underlying property” is presented and illustrated, supporting a syntactical principle appropriate to the detection of false digraph‐theoretic conjectures.
On finding steiner vertices
Authors: Rayward‐Smith V. J. , Clare A.
Published: May 2007

Given a graph G = (V, E), finding the Steiner tree in G for some set of special vertices V′ ⊂ V″, is equivalent to finding the minimum spanning tree in the subgraph of G induced by V′ ∪ V″, where V″ is the set of Steiner vertices. In this paper, we consider ways of deciding which vertices of V are in V″ and compare the performance of various heuristic algorithms.
Solving stochastic programs with network recourse
Authors: Wallace Stein W.
Published: May 2007

In this paper we provide computational procedures for solving stochastic programs with network recourse. Special attention is paid to the feasibility problem, and we show how to solve the recourse or second stage problem. This problem is how to solve a large number of networks where the only differences are the amounts supplied and demanded at the nodes. For this purpose we have developed the Schur complement for networks. Computational results are given. Finally we show how preprocessing based upon facet generation can simplify the rest of the procedures.
An algorithm for reliability analysis of planar graphs
Authors: Blenstock Daniel
Published: May 2007

We give an algorithm for the computation of K‐terminal reliability in planar graphs, whose worst‐case complexity is strictly exponential in the square root of the total number of nodes.
Graph folding and programmable logic array
Authors: Hu T. C. , Kuo Y. S.
Published: May 2007

The problem of compacting a programmable logic array is formulated as the following graph problem. Given a red‐edge bipartite graph, how to add maximum number of independent green edges such that there are no cycles formed by alternating red and green edges. For this NP‐complete problem, we present a polynomial heuristic algorithm which gives an optimum solution when the red bipartite graph satisfies certain conditions, e.g., a tree. When the bipartite graph does not satisfy these conditions, the heuristic algorithm gives a solution with worst‐case error bound. For a red bipartite graph with given cardinality, we give a tight upper bound on the number of green edges.
Problem reduction methods and a tree generation algorithm for the steiner network problem
Authors: Balakrishnan Anantaram , Patel Nitin R.
Published: May 2007

The Steiner network problem seeks a minimum weight connected subgraph that spans a specified subset off nodes in a given graph and optionally uses any of the other nodes as intermediate or Steiner points. This model has a variety of practical applications particularly in location, transportation, and communication planning. In this paper, we first outline some distinctive characteristics of optimal Steiner network solutions and propose a problem reduction procedure based on these properties. We derive a conservative estimate of the expected reduction achieved by this method under one set of probabilistic assumptions and demonstrate that this scheme produces asymptotically optimal reduction. We also report computational results for several randomly generated test problems. We then devise a tree generation algorithm that exploits the special structure of the Steiner network problem while solving its constrained minimal spanning tree formulation.
Steiner problem in networks: A survey
Authors: Winter Pawel
Published: May 2007

The problem of determining a minimum cost connected network (i.e., weighted graph) G that spans a given subset of vertices is known in the literature as the Steiner problem in networks. We survey exact algorithms and heuristics which appeared in the published literature. We also discuss problems related to the Steiner problem in networks.
A monte carlo sampling plan for estimating reliability parameters and related functions
Authors: Fishman George S.
Published: May 2007

Consider an undirected network G with node set V and arc set E = {1, …, n} where arcs fail randomly and independently. Let T be a subset of V and let Mk denote the number of ways that all the nodes of T are connected (T‐connectivity) with exactly k operating arcs and n ‐ k failed arcs. This paper describes a sampling plan for estimating {Mk} and linear functions of these parameters, including the T‐connectedness reliability function g(p) for common failure probability 1 ‐ p. Point and simultaneous interval estimates are derived for {Mk/(}, where the interval estimates meet a fixed width criterion in O(n log n) time as the size of the network n grows. Whereas all previously proposed Monte Carlo sampling plans enable one to estimate g(p) for a fixed p, the proposed method allows one to estimate the entire function {g(p), p ∈ P}, where either P = P* = {qi: O ≦ qi ≦ 1, 1 ≦ i = ≦ v} or P = P** = {[a, b]: 0 ≦ a ≦ b ≦ 1}. Here P* denotes a finite set of points in [0, 1] and P** an interval in [0, 1]. Simultaneous interval estimates are derived that meet a fixed width criterion in O(n) time for P = P* and in O(n2) time for P = P** as n → ∞. A priori bounds are also derived for g (p) and it is shown how these can be used to give guidance on the performance of the sampling plan. An example based on a network with 44 nodes and 85 arcs illustrates the proposed method.
Minimal deadlock‐free store‐and‐forward communication networks
Authors: Bongiovanni G. , Bovet D. P.
Published: May 2007

Store‐and‐forward communication networks may be designed so as to be free from store‐and‐forward deadlock. This is accomplished by incorporating in the network an acyclic buffer graph on which messages are forwarded, from buffer to buffer, according to all the desired routes. A technique producing minimum buffer graphs for a rather large class of networks is illustrated. Successively, a comparison is made with other well‐known deadlock avoidance techniques, showing that substantial savings can be achieved.
Neighbor‐connected graphs and projective planes
Authors: Gunther G. , Hartnell B. L. , Nowakowski R.
Published: May 2007

In [G. Gunther, Neighbor‐connectivity in regular graphs. Discrete Appl. Math. 11 (1985) 233–243] Gunther introduced the concept of a k neighbor‐connected graph, which has the property that the removal of any k − 1 closed neighborhoods neither disconnects the graph, nor leaves only a complete graph. In this paper we pursue the investigation of minimal graphs that are k‐regular in addition to being k neighbor‐connected. In a private communication, Gunther conjectured that if G is such a graph which contains no cliques of size larger than m, then |V(G)| ≧ k2 + (k + 1 − m) (k − 1) + 1. In the above reference, he proved that this conjecture is valid in the case that m = k and characterized the minimal graphs. In this paper, we begin to investigate the case where m = 2. We give some results connecting the minimal graphs to other combinatorial objects.
An algorithmic framework for the matching problem in some hypergraphs
Authors: Conforti Michele , Cornuejols Gerard
Published: May 2007

The matching problem in bipartite graphs can be solved by an elegant primal‐dual algorithm. The purpose of this paper is to introduce concepts which make it possible to generalize this algorithm to some classes of hypergraphs. We illustrate the approach by providing a polynomial primal‐dual algorithm for the matching problem in hypergraphs without odd cycles.
Accelerated branch exchange heuristics for symmetric traveling salesman problems
Authors: Stewart William R.
Published: May 2007

A method for accelerating the computational performance of branch exchange heuristics for symmetric traveling salesman problems (TSP's) is presented. The improvement in performance is obtained by considering only exchanges that have a good chance of producing a better solution. In the instance of the 3–optimal heuristic, the approach reduces the number of operations required to obtain a good solution to a TSP with N nodes from O(N3) to O(N2), without a corresponding degradation in the quality of the solution. Most of the results are produced for Euclidean TSP's, but evidence is presented that indicates that thes results apply equally well if not more strongly to the general symmetric TSP.
Linear placement algorithms and applications to VLSI design
Authors: Cheng Chung‐Kuan
Published: May 2007

A linear placement technique that uses an objective function of the sum of wiring lengths is proposed. The method evolves from well‐known concepts in job sequencing and network flow. The relation between a job sequencing problem and this linear placement problem was demonstrated by Lawler. Also, Sidney proposed decomposition algorithms for job sequencing problems. Building on Lawler's and Sidney's work, we first develop a polynomial‐time algorithm to obtain optimal solutions for the special case of parallel graphs. Adolphson and Hu applied the max‐flow min‐cut method of the network flow problem to the partitioning of general placement problems. However, when the cut operation creates the cut of the same configuration as the previous cut operations, no additional partitioning information is obtained. We devise an optimal graph modification that tries to change the configuration of the cut for further partitioning of the problem, and achieve the maximum partitioning of the problem. Finally, a heuristic algorithm is derived to solve some Very Large Scale Integrated Circuits (VLSI) design linear placement problems. A comparison with published papers shows that our VLSI placement method produces better results.
Minimum augmentation of a tree to a K‐edge‐connected graph
Authors: Ueno Shuichi , Kajitani Yoji , Wada Hajime
Published: May 2007

This paper solves the minimum augmentation problem for a given tree and positive integer k, that is, to make a tree k‐edge‐connected by adding the minimum number of edges. It is shown that the minimum number of edges is the least integer not less than a half of the deficiency of the tree which is defined as the sum of k‐(degree) over all the vertices whose degrees are less than k. The proof is constructive and gives a polynomial‐time algorithm for constructing such an augmentation.
Generalized de Bruijn digraphs
Authors: Du D. Z. , Hwang F. K.
Published: May 2007

We show that the digraphs proposed independently by Imase and Itoh, and Reddy, Pradhan and Kuhl to minimize diameters essentially retain all the nice properties of de Bruijn digraphs and yet are applicable to any number of nodes. In particular we give results on the number of loops, the link connectivities and connectivities, the embedding properties and the self‐routing properties for these digraphs.
The minimax multistop location problem on a tree
Authors: Berman O. , Simchi‐Levi D. , Tamir A.
Published: May 2007

In many services (e.g., delivery, or customer pickup vehicles) the service unit usually visits a number of demand points on a single multistop tour. Typically, at a specific time of the day, the unit receives the list of waiting calls and immediately starts a tour of the network that includes all waiting customers. The multistop location problem is to find the home location for the service unit. We focus on the minimax criterion for the multistop problem defined on a tree network. Each potential list of customers is associated with the length of its respective tour and with some weight. We seek for the home location of the unit that minimizes the maximum weighted tour length over all feasible customer lists. We consider several weight functions and obtain results that reveal additional properties of the classical absolute center of the tree.
The tolerance approach to sensitivity analysis in network linear programming
Authors: Ravi N. , Wendell Richard E.
Published: May 2007

The tolerance approach to sensitivity analysis, in contrast to classical sensitivity analysis, allows for simultaneous and independent perturbations of objective function coefficients and of right‐hand‐side terms from their original values. Here we specialize this approach to network problems. The specialization yields streamlined results in that the computations can be performed directly on a network.