bluuebunny/crossref_metadata_2025_split huggingface dataset:
A network decomposition/aggregation procedure for a class of multicommodity transportation problems
Authors: Evans James R. 
Published: May 2007

AbstractAn 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

AbstractIt 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

AbstractThe 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

AbstractThis 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

AbstractThe 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

AbstractThis 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

AbstractTwo 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

AbstractIn 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

AbstractWe 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

AbstractWe 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

AbstractUpper 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

AbstractLet 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.
Note on independence of arcs in antiparallel for network flow problems
Authors: Hagstrom Jane Nichols 
Published: May 2007

AbstractGiven 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

AbstractThis 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

AbstractLet 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

AbstractIn 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

AbstractLet 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

AbstractA 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

AbstractThe 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

AbstractIn 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

AbstractThe 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.
On finding steiner vertices
Authors: Rayward‐Smith V. J. , Clare A. 
Published: May 2007

AbstractGiven 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

AbstractIn 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.
Graph folding and programmable logic array
Authors: Hu T. C. , Kuo Y. S. 
Published: May 2007

AbstractThe 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

AbstractThe 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.
A monte carlo sampling plan for estimating reliability parameters and related functions
Authors: Fishman George S. 
Published: May 2007

AbstractConsider 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

AbstractStore‐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

AbstractIn [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

AbstractThe 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

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