bluuebunny/crossref_metadata_2025_split huggingface dataset:
A graph‐theoretic approach to investigate structural and qualitative properties of systems: A survey
Authors: Yamada Takeo , Foulds Leslie R. 
Published: May 2007

AbstractThis article presents a survey of the current status of the research on structural and qualitative systems theory that has been conducted in the last few decades. This theory can be traced back to the work of Samuelson on comparative static analysis of a national economy. His problem was to find the direction of change in economic equilibrium induced by small changes in the exogenous variables of a system based solely on qualitative information such as the sign pattern of the parameters that specify the system. In the field of engineering, the work of Iri et al. on structural analysis of systems of equations and Lin's research on the structural controllability of dynamic systems were quite influential. Following these pioneering works, a variety of research has been carried out by mathematicians and engineers, as well as by economists. A few examples of problems are the structural solvability and decomposability of systems of equations, the structural characterization of Tinbergen's rule of economic policy, the structural controllability and decouplability of dynamic systems, and the sign‐solvability of static systems. Using graph‐theoretic terms with explanatory examples, this paper surveys the established results on the structural and qualitative analysis of systems in areas ranging from control theory to economics.
Independence properties of directed markov fields
Authors: Lauritzen S. L. , Dawid A. P. , Larsen B. N. , Leimer H.‐G. 
Published: May 2007

AbstractWe investigate directed Markov fields over finite graphs without positivity assumptions on the densities involved. A criterion for conditional independence of two groups of variables given a third is given and named as the directed, global Markov property. We give a simple proof of the fact that the directed, local Markov property and directed, global Markov property are equivalent and – in the case of absolute continuity w. r. t. a product measure – equivalent to the recursive factorization of densities. It is argued that our criterion is easy to use, it is sharper than that given by Kiiveri, Speed, and Carlin and equivalent to that of Pearl. It follows that our criterion cannot be sharpened.
Medical diagnosis using influence diagrams
Authors: De Bragança Pereira Carlos Alberto , Barlow Richard E. 
Published: May 2007

AbstractInfluence diagrams are used to illustrate how the probability of having a disease can be updated given the results from two or more clinical tests. The problem of calibrating a register using results from a survey, as discussed by Heldal and Spjøtvoll (1988), is solved using a Bayesian approach.
A lower bound for the steiner tree problem in directed graphs
Authors: Liu Weiguo 
Published: May 2007

AbstractIn this article, we introduce a new integer programming formulation for the minimum Steiner tree problem in directed graphs. With the observation that every Steiner tree contains a two‐terminal Steiner tree for every pair of the terminals, our formulation is based on the linear programming formulation for the two terminal Steiner tree polyhedron obtained by Ball et al. [2]. By the results of Ball et al. [2], this formulation contains a large class of facets that are different from those induced by the well‐known Steiner cut constraints. We give a general form of the dual ascent algorithm and discuss the relationship between this algorithm and the projection method for extended formulations. This dual ascent algorithm is applied to the new formulation to obtain a lower bound for the minimum Steiner tree problem. In the algorithm, we use the dual ascent algorithm introduced by Wong [16] as a subroutine and improve his lower bound. Some computational results are given in Section 3.
Worst‐case greedy matchings in the unit d‐cube
Authors: Snyder Timothy Law , Steele J. Michael 
Published: May 2007

AbstractThe worst‐case behavior of greedy matchings of n points in the unit d‐cube, where d ≥ 2, is analyzed. The weighting function is taken to be the α'th power of Euclidean distance, where 0 < α < d. It is proved that the asymptotic growth rate of the weight of such a greedy matching is exactly βn(d‐α)/d, where β is a positive constant that depends on the parameters α and d. Included in the analysis is a minimax theorem equating the worstcase behaviors of matchings resulting from greedy algorithms that, when ordering edges for the greedy process, break ties in different ways.
The search game on a network with immobile hider
Authors: Anderson E. J. , Aramendia M. A. 
Published: May 2007

AbstractIn this paper we discuss a search game on a network, Q, with two players, a searcher and a hider. The hider chooses a point on Q at which to hide, while the searcher starts at a given point on Q and moves with continuous trajectory subject to a maximal speed. This is a zero‐sum game with payoff given by the time elapsed until the searcher reaches the point occupied by the hider. The solution to this game is known for certain types of network. Here by formulating the problem as an infinite‐dimensional linear program, we derive an algorithm for its solution. We discuss the performance of the algorithm on three examples.
The network simplex method on a multiprocessor
Authors: Peters Jörg 
Published: May 2007

AbstractWe compare several implemented approaches to parallelizing the network simplex method on the SEQUENT shared memory multiprocessor. The experiments underscore the importance of parallel pricing and show that specialized processes and single pivots are more efficient than are uniform processes with parallel pivots. We describe the PARNET implementation that combines the best features of the experimental codes. In its least parallel version, PARNET outperforms NETFLO, a standard sequential code, by a factor of 12. The total execution time (including i/o and statistics) for any problem with 5000 nodes and 25,000 arcs taken from a standard set of NETGEN benchmark problems is less than 25 sec wall clock time on the Sequent Symmetry S‐81 using six processors. The incremental speedup is linear up to six processors on the test set and improves with the problem size and the density of the underlying graph. For a problem with 1000 nodes and 500,000 ares, PARNET achieves incremental linear speedup up to 12 processors.
A network equilibrium formulation of market disequilibrium and variational inequalities
Authors: Nagurney Anna , Zhao Lan 
Published: May 2007

AbstractIn this article, we consider an asymmetric market disequilibrium model in a spatial setting in the case of rigid prices and/or controls. In this problem, the markets need no longer clear. We show that the disequilibrium problem can be reformulated as an equilibrium problem over an abstract network with special structure. We then propose a network decomposition algorithm for the computation of the solution that exploits the structure and establishes convergence results using the theory of variational inequalities. Our computational results demonstrate the suitability of this approach for large‐scale market problems.
Maximum matchings in bipartite graphs via strong spanning trees
Authors: Balinski M. L. , Gonzalez J. 
Published: May 2007

AbstractA new characterization of maximum matchings for bipartite graphs is presented. It is based on “strong spanning trees” and permits the development of a new algorithm that does not use the classical notion of augmenting paths and that runs in O(|V| |E|) time for bipartite graphs with |V| nodes and |E| edges.
Faster parametric shortest path and minimum‐balance algorithms
Authors: Young Neal E. , Tarjant Robert E. , Orlin James B. 
Published: May 2007

AbstractWe use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm.For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum‐balance algorithm of Schneider and Schneider.An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).
The generalized folding‐cube network
Authors: Choi Sang Bang , Somani Arun K. 
Published: May 2007

AbstractWe present an enhanced hypercube architecture and develop a corresponding routing scheme to realize arbitrary permutations in this paper. In particular, we design a rearrangeable and reconfigurable static hypercube architecture called the Generalized Folding‐Cube in the circuit switching environment. In the proposed hypercube, we show that if each connection between two neighboring nodes consists of two pairs of links (two full‐duplex communication lines) the hypercube can handle two independent permutations simultaneously. This hypercube architecture can also be used as an efficient reconfigurable network.
Reliability covering problems
Authors: Ball M. O. , Provan J. S. , Shier D. R. 
Published: May 2007

AbstractThis paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutive k‐out‐of‐n systems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang and Yao.
Average properties of two‐dimensional partial orders
Authors: Sidney J. B. , Sidney S. J. , Warburton A. 
Published: May 2007

AbstractThe complexity of many combinatorial algorithms is directly related to the number of upsets (filters) in an underlying partial order or, equivalently, to the number of downsets (ideals) that are the complements of upsets. In this paper, we investigate the expected number of upsets in randomly generated two‐dimensional partial orders and present a number of new results, together with simple combinatorial proofs of some known results. As an application of our results, we show that some well‐known algorithms for precedence constrained scheduling have nonpolynomial expected time and storage complexity.
Efficient algorithms for generalized cut‐trees
Authors: Gusfield Dan , Naor Dalit 
Published: May 2007

AbstractThe Gomory–Hu cut tree is a compact and efficiently computed representation of selected minimum edge cuts in a weighted undirected graph G = (V, E) with n nodes. It represents () minimum cuts, one for each pair of nodes in G, and can be constructed with only n − 1 flow computations. In this article, we generalize the types of cut‐trees that can be efficiently constructed. We solve the open problem, posed by Hu [9], of constructing with n − 1 flows a cut‐tree for minimum node weighted cuts in an undirected graph. We then show how to build cut‐trees that compactly represent the minimum edge cuts in directed graphs, partially solving the open problem of constructing cut‐trees for weighted edge cuts in directed graphs.
An optimal algorithm to solve the all‐pair shortest path problem on interval graphs
Authors: Ravi R. , Marathe Madhav V. , Pandu Rangan C. 
Published: May 2007

AbstractWe present an O(n2) time‐optimal algorithm for solving the unweighted all‐pair shortest path problem on interval graphs, an important subclass of perfect graphs. An interesting structure called the neighborhood tree is studied and used in the algorithm. This tree is formed by identifying the successive neighborhoods of the vertex labeled last in the graph according to the IG‐ordering.
Location of facilities on a network subject to a single‐edge failure
Authors: Eiselt Horst A. , Gendreau Michel , Laporte Gilbert 
Published: May 2007

AbstractIn this work, the following location problem is analyzed. Let N = (V,E) be an undirected connected simple network, where V is the vertex set, |V| = n and E is the edge set. There is a nonnegative demand wj associated with every vertex uj. It is assumed that every edge (ui,uj) has a probability of failure pij and that failures can never occur on two edges simultaneously. The problem consists of locating p facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so‐called leaf‐tree associated with the network. Third, when p = 1, the problem is a 1‐median problem. When p > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when p > 2, the problem with p + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with p facilities. An exact algorithm for this problem is described. It can be executed in either O(np + |E|) time or in O(n log n + |E|) time. A numerical example is provided.
Degenerate Gilbert—Steiner trees
Authors: Weng J. F. 
Published: May 2007

AbstractThe minimal Gilbert network problem is a generalization of the Steiner minimal tree problem derived by adding flow‐dependent weights to the edges. The minimal Gilbert network is referred to as a minimal Gilbert—Steiner tree if it has a Steiner topology. All trees with Steiner topologies, obtained by sequentially contracting edges connecting given points and their incident Steiner points, form a degenerate tree family. Similarly to the Steiner problem, a relatively minimal tree satisfying some angle conditions is referred to as a Gilbert–Steiner tree. This work shows that, unlike the Steiner problem, there may exist more than one Gilbert–Steiner tree in a degenerate tree family. It is proved that the maximum number of Gilbert–Steiner trees in a degenerate tree family is 2[(n−2)/2]. A necessary condition for the minimal Gilbert–Steiner tree is also given.
Two algorithms for the subset interconnection design problem
Authors: Prisner Erich 
Published: May 2007

AbstractAn NP‐complete generalization of the minimum spanning tree problem is considered. Given are a set of V, a cost function c: V × V → R+, and a collection {X1, …, Xm} of subsets of V. A graph G with vertex set V is called feasible if every Xi induces a connected subgraph of G. The minimum subset interconnection design problem is to find a feasible graph with a minimum cost sum. In this paper, two heuristic algorithms for the problem are given and analyzed. Several classes of input data for which one of the algorithms finds optimal or at least approximative solutions are presented.
The swapping problem
Authors: Anily S. , Hassin R. 
Published: May 2007

AbstractEach vertex of a graph initially may contain an object of a known type. A final state, specifying the type of object desired at each vertex, is also given. A single vehicle of unit capacity is available for shipping objects among the vertices. The swapping problem is to compute a shortest route such that a vehicle can accomplish the rearrangement of the objects while following this route. We exhibit several structural properties of shortest routes and develop polynomial approximation algorithms that are variations of a well‐known “patching” algorithm for the traveling salesman problem. We prove tight constant performance guarantees for these algorithms and note as a side product that these bounds hold and are tight also for the latter problem.
Reliabilities of chordal rings
Authors: Hu X. D. , Hwang F. K. 
Published: May 2007

AbstractA chordal ring is a degree‐3 regular graph with n vertices on a ring and n/2 chords determined by a parameter h. Chordal rings are attractive as topologies for computer networks due to their simple structures and short diameters. In this work, we study the reliabilities of chordal rings assuming each edge can independently fail with probability p. For p small, the usual criterion to measure the reliability of a network is its line‐connectivity. We show that all chordal rings have the same line‐connectivity and the same super line‐connectivity. We analyze the reliabilities of chordal rings by using the recently developed notions of isolated and nonisolated cutsets and list the optimal choices of h for n ≤ 30.
Scheduling file transfers in fully connected networks
Authors: Rivera‐Vega Pedro I. , Varadarajan Ravi , Navathe Shamkant B. 
Published: May 2007

AbstractWe consider the problem of transferring a set of files from their given locations in a fully connected network to their respective target locations in minimum time. We show that this problem is NP‐hard even with the restriction that no file uses more than two edges in its route. We present an efficient algorithm to solve this problem in the case when there is only one source and one or more destinations. For the general case, we propose a two‐phase approach to find two‐edge schedules that are optimal or close‐to‐optimal. In Phase I, two‐edge routes are assigned to files; in Phase II, a schedule is determined for the use of the links in these routes. For Phase I, we present an exact solution that is based on integer programming formulation and also give theoretical bounds for approximate solution. We also propose a route assignment algorithm that attempts to assign routes of minimum congestion. For Phase II, we present an efficient algorithm that constructs a schedule from the solution obtained in the first phase.
Finding disjoint paths with different path‐costs: Complexity and algorithms
Authors: Li Chung‐Lun , Thomas McCormick S. , Simchi‐Levi David 
Published: May 2007

AbstractConsider a network G = (V,E) with distinguished vertices s and t, and with k different costs on every edge. We consider the problem of finding k disjoint paths from s to t such that the total cost of the paths is minimized, where the jth edge‐cost is associated with the jth path. The problem has several variants: The paths may be vertex‐disjoint or arc‐disjoint and the network may be directed or undirected. We show that all four versions of the problem are strongly NP‐complete even for k = 2. We describe polynomial time heuristics for the problem and a polynomial time algorithm for the acyclic directed case.
The Capacitated Arc Routing Problem: Lower bounds
Authors: Benavent E. , Campos V. , Corberan A. , Mota E. 
Published: May 2007

AbstractIn this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds are compared on a set of test problems, are included.
Level graphs and approximate shortest path algorithms
Authors: Shapiro Jacob , Waxman Jerry , Nir Danny 
Published: May 2007

AbstractShortest path algorithms for graphs have been widely studied and are of great practical utility. For the case of a general graph, Dijkstra's algorithm is known to be optimal. However, in many practical instances, there is a “level” structure which may be imposed on the underlying graph. Utilizing these levels, this paper demonstrates that the time complexity of shortest path generation may be greatly reduced.A new graph structure, the level graph, together with a simple uniformed heuristic, LGS, for searching that structure is introduced, which allows for rapid generation of approximate shortest paths. LGS is studied both analytically and via simulation. It is shown that the length of the path produced by LGS converges rapidly to that of the actual shortest path as the distance between the points increases.
Efficient parallel algorithms for bipartite permutation graphs
Authors: Chen Lin , Yesha Yaacov 
Published: May 2007

AbstractIn this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others. All these problems can be solved inO(log2n) time withO(n3) processors on a Common CRCW PRAM. We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm. ©1993 by John Wiley & Sons, Inc.
A two‐stage network with dual partial concentrators
Authors: Hwang F. K. , Richards G. W. 
Published: May 2007

AbstractA two‐stage rearrangeable broadcast network (called an ordinary network here) that has been studied recently has a partial concentrator on the input side. We extend this study to a network with two partial concentrators: one on the input side and the other on the output side. We first study the network as a connection network and derive conditions for its rearrangeability. We show that the conditions are tight in some cases. We then show that a particular construction that meets the rearrangeability conditions actually yields a broadcast network. © 1993 John Wiley & Sons, Inc.
Doubly chordal graphs, steiner trees, and connected domination
Authors: Moscarini M. 
Published: May 2007

AbstractA new class of chordal graphs, containing the class of strongly chordal graphs, is introduced. It is shown that these graphs, called doubly chordal graphs, are related to acyclic hypergraphs and are recognizable in polynomial time. Furthermore, after proving that the Steiner tree and the connected domination problems are polynomially solvable for doubly chordal graphs, it is shown that both problems are NP‐hard for a class of chordal graphs (called Helly chordal graphs) containing the class of doubly chordal graphs. © 1993 John Wiley & Sons, Inc.
Local broadcasting in a tree under minisum criterion
Authors: Koh Jae‐Moon , Tcha Dong‐Wan 
Published: May 2007

AbstractThis paper is concerned with information dissemination in a tree. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time. Under a minisum criterion, a necessary and sufficient condition for an optimal call sequence at each vertex is established. Based on this, an O(N log N) algorithm is designed to find optimal call sequences at all vertices and to determine the broadcast center of a tree—the set of all vertices from which minisum broadcasting can be accomplished. © 1993 John Wiley & Sons, Inc.