bluuebunny/crossref_metadata_2025_split huggingface dataset:
A recognition algorithm for the total graphs
Authors: Gavril F. 
Published: May 2007

AbstractA graph H is called total if there exists a graph G such that there is a one‐to‐one correspondence between the vertices of H and the vertices and edges of G such that two vertices of H are adjacent iff the corresponding elements of G are adjacent or incident.In this paper we present a linear time algorithm for the recognition of the total graphs. The algorithm is based on the breadth‐first search technique.
A generalized measure of independence and the strong product of graphs
Authors: Barnes B. H. , Mackey K. E. 
Published: May 2007

AbstractThis work extends the results of M. Rosenfeld [6] on universal graphs with respect to the strong graph product. By using a generalized measure of independence, one can get improved bounds on the growth of the maximum independent set size under this graph product. Furthermore, a necessary and sufficient condition is derived for when the maximum independent set of the product graph is strictly greater than the product of the maximum independent sets.
Generalized ramsey theory for graphs VII: Ramsey numbers for multigraphs and networks
Authors: Harary F. , Schwenk A. J. 
Published: May 2007

AbstractRamsey problems are examined for the different varieties of graphs and digraphs, with and without loops and multiple edges, and even for networks. In every case, the resulting Ramsey number either fails to exist, or has a trivial value, or equals the value for the underlying graph or digraph. Thus it appears there are no new interesting Ramsey numbers for multigraphs and networks.
The complexity of the network design problem
Authors: Johnson D. S. , Lenstra J. K. , Kan A. H. G. Rinnooy 
Published: May 2007

AbstractIn the network design problem we are given a weighted undirected graph. We wish to find a subgraph which connects all the original vertices and minimizes the sum of the shortest path weights between all vertex pairs, subject to a budget constraint on the sum of its edge weights. In this note we establish NP‐completeness for the network design problem, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees. This result justifies the development of enumerative optimization methods and of approximation algorithms, such as those described in a recent paper by R. Dionne and M. Florian.
Complexity of the minimum‐dummy‐activities problem in a pert network
Authors: Krishnamoorthy M. S. , Deo N. 
Published: May 2007

AbstractAny complex project consists of a number of activities which are carried out in some specified precedence order. One of the factors that is considered is in minimizing the project completior, time. The computation of the optimum project completion time is proportional to the number of edges, including dummy activities. In the past, many algorithms were proposed to yield minimum number of dummy activities required to satisfy the given precedence relation. In this paper we transform the node‐cover problem in graphs of degree at most 3 to the minimum‐dummy‐activities problem. Using this transformation we show that the minimum‐dummy‐activities problem in a PERT network is NP‐complete. The significance of this result is that it is worthwhile in developing a polynomial time heuristic algorithm for solving the dummy activities problem.
Minimum‐time line broadcast networks
Authors: Farley Arthur M. 
Published: May 2007

AbstractBroadcasting refers to the process of message dissemination in a communication network whereby a message, originated by one member, becomes known to all members. Line broadcasting assumes that members may “switch‐through” any number of calls during a time unit. An algorithm is presented which produces a calling schedule completing line broadcasting in minimum time from any member of any tree. A discussion of three types of broadcasting and their associated minimum time networks is included.
A theorem concerning cyclic directed graphs with applications to network reliability
Authors: Willie Randall R. 
Published: May 2007

AbstractIn a recent paper, Satyanarayana and Prabhakar have presented a new topological formula for evaluating exact reliability of terminal‐pair directed networks. Terms in the formula are associated in a one‐to‐one fashion with certain acyclic subgraphs of the network, cyclic subgraphs being of no importance. In their paper, however, the proof that cyclic subgraphs may be ignored seems to be incomplete. We consider an alternate proof of this fact.
A probabilistic model for the analysis of the routing process for circuits
Authors: Agrawal P. , Breuer M. A. 
Published: May 2007

AbstractA 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

AbstractWe 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

AbstractThe 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

AbstractPrevious 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

AbstractA 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

AbstractLocating 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

AbstractIn 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

AbstractGiven 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

AbstractThe 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

AbstractIn 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

AbstractA 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

AbstractThe 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

AbstractWe 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

AbstractAn 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

AbstractIn 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

AbstractTwo 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

AbstractA 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

AbstractProblems 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

AbstractThe 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

AbstractIn 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

AbstractThis 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

AbstractIn 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

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