bluuebunny/crossref_metadata_2025_split huggingface dataset:
Deferral strategies for a dynamic communications network
Authors: Smith R. L. 
Published: May 2007

AbstractThis paper deals with the problem of minimizing the present worth of expenditures for the expanding the capacity of a communications network in the face of an increasing demand for service. It is assumed that any economy of scale effects are dominated by savings due to expenditure deferral. A strategy is proposed that defers new construction of facilities by heuristic routing around exhausted facilities. Network solutions obtained by the deferral heuristic applied to a small prototype network compare favorably with exact solutions obtained by solving the underlying mixed integer LP.
A boolean theory of network flows and metrics and its applications to particle transmission and clustering
Authors: Onaga K. , Mayeda W. 
Published: May 2007

AbstractA network N considered here is a graph (G,E) whose edge e is weighted by I(e) = [α(e), β(e)]. An admissible flow is a flow f satisfying α(e) ⊆ f (e) ⊆ β(e), for all e ⊂ E. A necessary and sufficient condition for existence of admissible Boolean flows in N, and characterization of maximum Boolean flows are presented. Then a property of maximum Boolean flows which are the terminal capacities of two‐terminal Boolean flows satisfy a Boolean triangular inequality is shown. Finally the concept of γ‐relativeness of a symmetric Boolean mapping m for any threshould γ⊆ S which induces a cluster decomposition of the node set V, by introducing Boolean network metrics is presented.
A cut‐flow procedure for transportation network optimization
Authors: Peterson Bruce E. 
Published: May 2007

AbstractMany transportation network optimization problems use conservation of flow equations as constraints when a network must accommodate set flows between nodes. A different set of equations, called cut‐flow constraints, is developed to replace the conservation of flow equations. These constraints require that the flow over every separating cut be at least equal to total traffic requirements between nodes separated by the cut. In many network problems the cut‐flow constraints may prove more efficient than existing multicommodity formulations. The cut‐flow constraints are applied to the optimization problem of minimizing the sum of fixed and variable costs in a network.
Maximal expected flow in a network subject to arc failures
Authors: Aneja Y. P. , Nair K. P. K. 
Published: May 2007

AbstractIn a network subject to arc failures, each chain has a probability of failure. Therefore the maximal flow in the network is a random variable. The problem considered here is that of maximizing the expected flow. An arc‐chain formulation of the problem, and an algorithm for computing an optimal solution are provided. The algorithm involves a column generation technique, and a constrained chain in the network provides a desired column at each step of the simplex algorithm. The technique presented here is an extension of that of Ford and Fulkerson. The algorithm is validated, and a geometric interpretation is included.
Four‐terminus flows
Authors: Seymour P. D. 
Published: May 2007

AbstractSuppose that s1, s2, s3, s4 are vertices of a graph, that each edge has a real‐valued capacity, and qii(1 ⩽ i < j ⩽ 4) are six demands. There exist flows from si to sj of value qij(1 ⩽ i < j ⩽ 4), such that the total flow through each edge does not exceed its capacity, if and only if the obvious connectivity requirements are satisfied. This result extends Hu's 2‐commodity flow theorem.
An algorithm for the traffic assignment problem
Authors: Weintraub Andrés , González Jaime 
Published: May 2007

AbstractAn optimization algorithm for the traffic assignment problem is presented. It is based on determining, for the flow corresponding to each origin at a time, a set of disjoint circuits with the most negative total marginal cost, followed by a unidimensional optimization along these circuits. The proposed method was compared to other well known approaches on randomly generated networks. In most cases the proposed method proved to be highly efficient, particularly when appropriate tighter stopping rules were used. In this sense, it was seen that when stopping rules were based on insufficiently tight tolerances, substantial errors could appear in the equilibrium traffic assignment.
Optimal clustering structures for hierarchical topological design of large computer networks
Authors: Kleinrock Leonard , Kamoun Farouk 
Published: May 2007

AbstractLarge packet switching computer networks on the order of hundreds or thousands of nodes will soon emerge to handle the fast‐growing demands in data communication and resource sharing among various information processing systems around the world. The network topology design problem has long been recognized as extremely complex and very quickly becomes unmanageable as the size of the network increases. Existing heuristic design procedures are quite efficient for the design of small to moderate‐sized networks (25–75 nodes); however, they become very costly and even prohibitive when dealing with large networks. A design methodology based on the hierarchical clustering of the network nodes is presented in this paper in order to alleviate the computational cost involved in the design. More specifically, the emphasis is on the determination of a clustering structure which minimizes the computational cost of the design. Such a cost is assumed to have a polynomial growth with the number of nodes in the subnet to be designed. We present optimum results both for the number of clusters, number of superclusters, etc., and for the number of hierarchical levels. An expression for the average delay of a message in such a hierarchical network is also provided in terms of the average delays in the subnets composing the network. This decomposition leads to the design of smaller subnetworks for which we can utilize present design strategies.
An O(n log n) heuristic for steiner minimal tree problems on the euclidean metric
Authors: Smith J. Macgregor , Lee D. T. , Liebman Judith S. 
Published: May 2007

AbstractAn O(n log n) heuristic for the Euclidean Steiner Minimal Tree (ESMT) problem is presented. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the Delaunay triangulation, then “recomposes” the suboptimal Steiner Minimal Tree (SMT) according to the Voronoi diagram and Minimum Spanning Tree (MST) of the point set. The ESMT algorithm was implemented in FORTRAN‐IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the O(n log n) algorithm with an O(n4) algorithm clearly indicates that the O(n log n) algorithm is as good as the previous O(n4) algorithm in achieving reductions in the ratio SMT/MST of the given vertex set. This is somewhat surprising since the O(n4) algorithm considers more potential Steiner points and alternative tree configurations.
Sensitivity analysis of optimal matchings
Authors: Weber G. M. 
Published: May 2007

AbstractAfter stating the weighted, perfect matching problem and briefly describing Edmonds' algorithm, certain postoptimality procedures are described. These procedures aid in reoptimizing related matching problems in which a few edge weights are altered. Regardless of the actual implementation of the matching algorithm used, when changing a single edge weight, the postoptimality procedures are on the order of cardinality (N) more efficient than solving the modified problem “from scratch,” where N is the node set of the underlying graph.
A generalized assignment heuristic for vehicle routing
Authors: Fisher Marshall L. , Jaikumar Ramchandran 
Published: May 2007

AbstractWe consider a common variant of the vehicle routing problem in which a vehicle fleet delivers products stored at a central depot to satisfy customer orders. Each vehicle has a fixed capacity, and each order uses a fixed portion of vehicle capacity. The routing decision involves determining which of the demands will be satisfied by each vehicle and what route each vehicle will follow in servicing its assigned demand in order to minimize total delivery cost. We present a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost. This heuristic has many attractive features. It has outperformed the best existing heuristics on a sample of standard test problems. It will always find a feasible solution if one exists, something no other existing heuristic can guarantee. It can be easily adapted to accommodate many additional problem complexities. By parametrically varying the number of vehicles in the fleet, our method can be used to optimally solve the problem of finding the minimum size fleet that can feasibly service the specified demand.
Exact solution of crew scheduling problems using the set partitioning model: Recent successful applications
Authors: Marsten Roy E. , Shepardson Fred 
Published: May 2007

AbstractThe set partitioning model of the crew rotation problem has been well known for many years. This paper focuses on recent developments that have made this model more attractive and have resulted in several successful implementations. These developments include improved problem conceptualizations and decompositions, as well as new solution techniques employing Lagrangian relaxation and subgradient optimization. Experience is reported from The Flying Tiger Line, Pacific Southwest Airways, Continental Airlines, and Helsinki City Transport. A case is made for work on heuristic decomposition methods to break large problems into moderate sized pieces that can be solved exactly.
Generalizations of Hoffman's existence theorem for circulations
Authors: Hassin Refael 
Published: May 2007

AbstractHoffman's Existence Theorem for circulations gives a necessary and sufficient condition for the existence of a feasible circulation in a directed network with upper and lower bounds on the flow along each of the arcs. This paper presents new existence theorems for more general types of flows in directed networks: flows with gains, two‐commodity flows, and flows with set constraints.
Finding maximum cliques in circle graphs
Authors: Rotem D. , Urrutia J. 
Published: May 2007

AbstractA circle diagram consists of a circle C and a set of n chords. This diagram defines a graph with n vertices where each vertex corresponds to a chord, and two vertices are adjacent if their corresponding chords intersect in C. A graph G is called a circle graph if it is defined by some circle diagram. An algorithm which requires O(n2) steps to generate one maximum clique is presented. The algorithm can also be used to generate all maximum cliques where the number of steps need to generate each additional maximum clique is linear in its size. This compares favourably with Gavril's algorithm [4] which works in O(n3) steps.
A new concept of primeness in graphs
Authors: Lamprey R. H. , Barnes B. H. 
Published: May 2007

AbstractA graph is quasiprime with respect to a boolean product of graphs if whenever it is a subgraph of the product of two graphs, it must necessarily be isomorphic to a subgraph of one of its factors. This paper provides a characterization of graphs quasi‐prime with respect to cartesian product, as well as graphs quasiprime with respect to other products.
Finding minimum rectilinear distance paths in the presence of barriers
Authors: Larson Richard C. , Li Victor O. K. 
Published: May 2007

AbstractGiven a set of origin‐destination points in the plane and a set of polygonal barriers to travel, this paper develops an efficient algorithm for finding minimal distance feasible paths between the points, assuming that all travel occurs according to the rectilinear distance metric. By geometrical arguments the problem is reduced to a finite network problem. The nodes are the origin‐destination points and the barrier vertices. The links designate those node pairs that “communicate” in a simple way, where communication implies the existence of a node‐to‐node rectilinear path that is not made longer by the barriers. The weight of each link is the rectilinear distance between its two corresponding nodes. Solution of the minimal distance path problem on the network procedes in two steps. First, for a given origin or root node, a tree is generated containing a minimal distance path to each node that communicates with the root node. Second, a modified Dijkstra‐type iteration is utilized, starting with the nodes of the tree, sequentially adding nodes according to minimum “penalty distance,” where the penalty is the extra travel distance caused by the barriers. The paper concludes with a discussion of the computational complexity of the procedure, followed by a numerical example.
Combinatorial properties of directed graphs useful in computing network reliability
Authors: Satyanarayana A. , Hagstrom Jane N. 
Published: May 2007

AbstractThis paper is concerned with the problem of computing the probability that a root vertex can communicate with all other vertices in a probabilistic directed graph. One method is to apply the inclusion‐exclusion principle of probability theory to the event “at least one rooted spanning tree of the graph is working.” We prove combinatorial properties of graphs which allow us to derive a much condensed form of the inclusion‐exclusion expression. Each term corresponds to an acyclic spanning subgraph of the original graph, with coefficient equal to (−1)b‐n+1, where b and n are the number of edges and vertices of the subgraph, respectively.
Mazes: Search games on unknown networks
Authors: Anderson E. J. 
Published: May 2007

AbstractThis paper discusses a class of search problems on networks, where the searcher only has information about that part of the network which he has traversed. These problems correspond to that of finding the exit of a maze. In this context it is natural to consider the two person game between the solver and the setter, where the setter may choose the maze subject to a constraint on the total length of its arcs. A particular strategy for the solver is investigated and shown to be optimal for this game.
Some theoretical results in multiple path definition in networks
Authors: Moss Franklin H. , Merlin Philip M. 
Published: May 2007

AbstractThis paper is concerned with the problem of defining K multiple paths between pairs of nodes in a network. The treatment presented here is on a theoretical level, although the problem is motivated by a practical scheme for message routing in store‐and‐forward packet switched computer networks. Theorems are presented which offer readily testable sufficient conditions on the topology of a network which guarantee the existence of at least one set of paths under consideration. The proof of this theorem provides a generalized systematic method for constructing these paths if the sufficient conditions are met.
Minimum cost flow with set‐constraints
Authors: Hassin Refael 
Published: May 2007

AbstractThe minimum cost network flow problem with set‐constraints is a generalization of the well‐known minimum cost network flow problem, in which bounds on the sum of flows through sets of arcs exist. This paper investigates some variations of this problem, including the polymatroid intersection problem, where for each node two polymatroids are given; one polymatroid constrains flows entering the node, and the other constrains flows leaving it.
A decomposition algorithm for locating a shortest path between two nodes in a network
Authors: Jarvis John J. , Tufekci Suleyman 
Published: May 2007

AbstractA decomposition algorithm for locating a shortest path between two nodes of a network with circuits (directed cycles) and arbitrary arc distances (with the customary assumption of no negative circuits) is introduced. Unlike similar decomposition algorithms by Hu [12, 13], Yen [23], and Glover, Klingman, and Napier [10], this algorithm finds only the shortest distance between two specified nodes. Computational complexity of this algorithm is shown to be better than the previous decomposition algorithms.
An algorithm for the equilibrium assignment problem with random link times
Authors: Sheffi Yosef , Powell Warren B. 
Published: May 2007

AbstractIn this article we offer an equivalent minimization formulation for the traffic assignment problem when the link travel times are flow‐dependent random variables. The paper shows the equivalency between the first‐order conditions of this program and the stochastic equilibrium conditions as well as the uniqueness of the solution. The paper also describes an algorithmic approach to the solution of this program, including a proof of convergence. Finally, we conduct some limited numerical experiments on the rate of convergence of the algorithm and the merits of the stochastic equilibrium model, in general, as compared with deterministic approaches.
On balance in group graphs
Authors: Harary Frank , Lindström Bernt , Zetterström Hans‐olov 
Published: May 2007

AbstractWe propose a generalization of signed graphs, called group graphs. These are graphs regarded as symmetric digraphs with a group element s(u, v) called the signing associated with each arc (u, v) such that s(u, v) s (v, u) = 1. A group graph is balanced if the product s(v1, v2) s (v2, v3) …s(um, v1) = 1 for each cycle v1, v2,…, vm, v1 in the graph. Let G denote the graph, F the group (not necessarily commutative), and s the signing. Then the group graph is denoted by (G, F, s). Given a group graph (G, F, s), which need not be balanced, we define the deletion index δ(G, F, s) as the minimum cardinality of a deletion set, which is a subset of lines whose deletion results in a balanced group graph. Similarly we define the alteration index γ(G, F, s) as the minimum cardinality of a alteration set, which is a set of lines {u, v} in the graph the values s(u, v) and s(v, u) of which can be changed so that the new group graph is balanced. When F is the group of order 2, we obtain a signed graph. Generalizing results known for signed graphs, we prove that minimal deletion sets are minimal change sets, which implies the equality δ(G, F, s) = γ(G, F, s) for all G, F, and s. We also prove the in‐equality δ (G, F, s) ≤ (n ‐ 1)q/n, where q is the number of lines in the graph G and n is the order of the group F. We conclude by studying δ for signed complete bigraphs Kn,n when the signing is determined from a Hadamard matrix.
The generalized diameter of a graph
Authors: Chen Chih‐Kang Eric , Garfinkel R. S. 
Published: May 2007

AbstractWe generalize the concept of the diameter of a graph G = (N, A) to allow for location of points not on the nodes. It is shown that there exists a finite set of candidate points which determine this generalized diameter. Given the matrix of shortest paths, an o (|A|2) algorithm is developed and tested.
Realizability of p‐point, q‐line graphs with prescribed point connectivity, line connectivity, or minimum degree
Authors: Boesch F. T. , Suffel C. L. 
Published: May 2007

AbstractIt is well known that certain graph‐theoretic extremal questions play a central role in the study of information network vulnerability. These extremal problems are special cases of the general question of realizability of graph invariants. For example a (p, Δ, δ, λ) graph is a graph having p‐points, maximum degree Δ, minimum degree δ, and line‐connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, γ) realizable if there is a (p, Δ, δ, γ) graph with p = a, Δ = b, δ = c, and γ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, γ) realizable were recently given by the authors. In another manuscript they gave the solution to (p, Δ, δ, k) realizability, where k denotes the point connectivity. In this work we give necessary and sufficient conditions for (p, q, k), (p, q, γ), and (p, q, δ) realizability, where q denotes the number of lines of a graph.
A matroid related to finitely chainlike, countably infinite networks
Authors: Tucker A. C. , Zemanian A. H. 
Published: May 2007

AbstractThe determination of the currents and voltages in a countably infinite electrical network containing infinite energy requires not only the imposition of Kirchoff's laws and Ohm's laws but also the arbitrary assignment of the current‐voltage pairs in certain sets of branches, called joints. For finitely chainlike, countably infinite networks the maximal joint sets satisfy the base axioms of a matroid.
A property regarding degenerate pivots for linear assignment networks
Authors: Bazaraa Mokhtar S. , Sherali Hanif D. 
Published: May 2007

AbstractGiven an extreme point of an assignment polytope of size m, there exist 2m−1 mm−2 alternative basis representations according to the choice of the m ‐ 1 degenerate basic variables. This note establishes the basis structure which admits the maximum degenerate pivots and that which admits the minimum degenerate pivots. It is shown that the upper bound is achieved if and only if the basis is a chain graph and that the lower bound is achieved if the degenerate basic arcs all originate at some facility or all terminate at some location.
An advanced dual incremental network algorithm
Authors: Schmidt Stephen R. , Jensen Paul A. , Barnes J. Wesley 
Published: May 2007

AbstractAn extensive literature survey reveals that computational analyses of pure minimumcost‐network algorithms do not address the use of dual incremental codes. Previous studies only compare dual‐arc‐infeasible‐, primal‐dual‐, and primal‐type network codes. Of these three types, the primal method has been shown to be computationally superior to the other methods. This paper surveys the historical development of the dual incremental method up to and including the code DUALINC. Following a comprehensive description of DUALINC, a computational comparison is made with three other recently publicized codes, two primal codes and a dual‐arc‐infeasible code. The results of this comparison reveal that the new dual incremental code is much more efficient than the dual‐arc‐infeasible code and that it is competitive with the primal codes.
Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
Authors: Reingold Edward M. , Supowit Kenneth J. 
Published: May 2007

AbstractThe expected costs of the matchings found by various divide‐and‐conquer heuristic algorithms are calculated, under the assumption that the vertices to be matched are uniformly distributed in the unit square. The expected times of the algorithms are calculated as well.
Heuristics for planar minimum‐weight perfect metchings
Authors: Iri Masao , Murota Kazuo , Matsui Shouichi 
Published: May 2007

AbstractSeveral linear‐time approximation algorithms for the minimum‐weight perfect matching in a plane are proposed, and their worst‐ and average‐case behaviors are analyzed theoretically as well as experimentally. A linear‐time approximation algorithm, named the “spiral‐rack algorithm (with preprocess and with tour),” is recommended for practical purposes. This algorithm is successfully applied to the drawing of road maps such as that of the Tokyo city area.