bluuebunny/crossref_metadata_2025_split huggingface dataset:
Shortest path algorithms using dynamic breadth‐first search
Authors: Goldfarb Donald , Hao Jianxiu , Kai Sheng‐Roan 
Published: May 2007

AbstractA new O(nm) label‐correcting algorithm is presented for finding shortest paths from a given node to all other nodes in a network of n nodes and m arcs or finding a directed cycle of negative length. In this algorithm, a node is scanned on the k‐th scanning step only if its “label depth”—i.e., the length of the path corresponding to the distance label—equals k. Variants of this algorithm are discussed, and computational results show that several of these are very efficient. A new criterion for detecting a negative cycle that is also based on the label depth of a node is given, and computational tests show that it is extremely effective.
On the multiway cut polyhedron
Authors: Chopra Sunil , Rao M. R. 
Published: May 2007

AbstractGiven a graph G = (V,E) and a set N ⊆ V, we consider the problem of finding a minimum‐weight multiway cut that separates each pair of nodes in N. In this paper we give an integer programming formulation of this problem and study the associated polyhedron. We give some computational results to support the strength of our facets. We also give some efficiently solvable instances.
Consistency and satisfiability of waveform timing specifications
Authors: Brzozowski J. A. , Gahlinger T. , Mavaddat F. 
Published: May 2007

AbstractManufacturers often use digital waveforms to specify critical device timing. In this paper, we study two problems related to the use of such specifications. First, we are interested in verifying that the timing information is consistent to begin with. Second, given waveform specifications of two devices that are to be linked, we wish to know whether one satisfies the other's timing requirements. We construct a model of the timing information conveyed by the waveform convention and show how both problems can be solved efficiently with optimization techniques. To illustrate our arguments, we compare the write‐cycle timing of a typical CPU with that of a RAM device.
Unbalanced, capacitated p‐median problems on a chain graph with a continuum of link demands
Authors: Sherali Hanif D. , Rizzo Thomas P. 
Published: May 2007

AbstractThis article is concerned with the problem of locating p capacitated facilities on a chain graph and simultaneously determining the allocation of their supplies in order to satisfy a continuum of demand. The demand is characterized by some weighted probability density functions defined on the chain graph. The objective is to minimize the total (expected) trnasportation cost. This location‐allocation problem is also referred to as the capacitated p‐median problem on a chain graph. Two unbalanced cases of this problem are considered, namely, the overcapacitated case when total supply exceeds total demand and the deficit capacity case when total supply is less than total demand. Both these problems are nonconvex and are shown to be NP‐hard even if the demand density function is piecewise uniform and positive. We provide a first‐order characterization of optimality for these two problems and prescribe an enumerative algorithm based on a partitioning of the dual space in order to optimally solve these problems. An extension of these algorithms for solving the unbalanced, capacitated 2‐median problem on a tree graph is also given.
On the existence of uniformly optimally reliable networks
Authors: Boesch F. T. , Li X. , Suffel C. 
Published: May 2007

AbstractA well‐known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. The measure of reliability is then defined to be the probability that the graph is connected. A well‐defined synthesis problem is to find the graph that minimizes the failure probability given the number of nodes n, the number of edges e, and the edge failure rate ρ. In this work, we consider the possibility of the existence of a fixed graph that is optimal for all possible ρ. It is simple to verify that such graphs exist when e = n − 1, or n. Herein, we show that they also exist when e = n + 1 and n + 2.
Polynomial time algorithms on circular‐arc overlap graphs
Authors: Kashiwabara Toshinobu , Masuda Sumio , Nakajima Kazuo , Fujisawa Toshio 
Published: May 2007

AbstractLet S be a family of arcs on a circle. A graph G = (V,E) is called a circular‐arc overlap graph for S if (i) there is a one‐to‐one correspondence between V and S and (ii) two vertices in V are adjacent if and only if the corresponding arcs in S intersect but neither one of them contains the other. In this article, we present two polynomial time algorithms on circular‐arc overlap graphs. Given a circular‐arc overlap graph in the form of a family of n arcs, the first algorithm obtains a maximum independent set in O(n2) time and the second one finds a maximum clique in O(n5) time.
Parametric analysis of optimal facility locations
Authors: Brandeau Margaret L. , Chiu Samuel S. 
Published: May 2007

AbstractWe summarize recent results for parametric analysis of optimal facility locations and report on a number of solved and unsolved problems. We describe general conditions that yield tractable parametric analyses of location problems. We present a methodology for parametric analysis of tree network and planar location problems, as well as illustrative analyses for selected problems. Finally, we discuss current and promising research in this area.
Conditional graph connectivity relative to hereditary properties
Authors: Oellermann Ortrud R. 
Published: May 2007

AbstractA graphical property P is said to be hereditary (strongly hereditary) if every induced subgraph (subgraph) of a graph with property P also has property P. If P is a graphical property, then the P‐connectivity of a graph is the minimum number of vertices whose removal from G produces the trivial graph or a disconnected graph each of whose components has property P. Several analogs and generalizations of results concerning the ordinary connectivity of a graph are established for the P‐connectivity of a graph, with respect to hereditary properties P. If P is a graphical property, then the P‐edge‐connectivity of a graph is defined similarly to the P‐connectivity. Several results concerning the P‐edge‐connectivity of a graph with respect to strongly hereditary properties P are established. Moreover, a generalization of Whitney's inequalities is given.
Euclidean shortest path in the presence of obstacles
Authors: Chen Yong‐Mao , Ramanan Prakash 
Published: May 2007

AbstractWe consider the problem of finding the (Euclidean) shortest path SP(s, t) between two points s and t in the plane, in the presence of obstacles. Lee and Preparata considered a special case, where the obstacles are n disjoint segments parallel to the y‐axis. Let V be the set consisting of s, t and the endpoints of the n segments. They showed that the shortest path between s and any point in V is monotone with respect to the x‐axis. Let SPT(V) denote the Shortest Path Tree on V that consists of the shortest path from s to each point in V. They presented an O(n log n) algorithm for constructing SPT(V) and an Ω(n log n) lower bound for finding SP(s, t). Their algorithm first sorts the segments according to their abscissae and then constructs SPT(V) by sweeping a vertical line from s to t. Their lower bound proof is based on the fact that any algorithm that finds SP(s, t) must actually sort the segments according to their abscissae. We prove that even if the segments are given in sorted order of their abscissae, Ω(n log n) time is still required to find SPT(V). The sweep‐line technique for finding SP(s, t) can be used whenever SP(s, t) is monotone. Lee and Preparata stated that SP(s, t) is monotone for arbitrary obstacles, if the projections of any two obstacles on the x‐axis do not overlap. We prove that SP(s, t) is monotone if the projections of any two obstacles do not partially overlap, and s and t are, respectively, to the left and to the right of all the obstacles.
Minimum weight paths in time‐dependent networks
Authors: Orda Ariel , Rom Raphael 
Published: May 2007

AbstractWe investigate the minimum weight path problem in networks whose link weights and link delays are both functions of time. We demonstrate that, in general, there exist cases in which no finite path is optimal leading us to define an infinite path (naturally, containing loops) in such a way that the minimum weight problem always has a solution. We also characterize the structure of an infinite optimal path. In many practical cases, finite optimal paths do exist. We formulate a criterion that guarantees the existence of a finite optimal path and develop an algorithm to find such a path. Some special cases, e.g., optimal loopless paths, are also discussed.
Resilience of partial k‐tree networks with edge and node failures
Authors: Mata‐Montero Erick 
Published: May 2007

AbstractThe resilience of a network is the expected number of pairs of nodes that can communicate. Computing the resilience of a network is a #P‐complete problem even for planar networks with fail‐safe nodes. We generalize an O(n2) time algorithm to compute the resilience of n‐node k‐tree networks with fail‐safe nodes to obtain an O(n) time algorithm that computes the resilience of n‐node partial k‐tree networks with edge and node failures (given a fixed k and an embedding of the partial k‐tree in a k‐tree).
On the nonexistence of uniformly optimal graphs for pair‐connected reliability
Authors: Amin A. T. , Siegrist K. T. , Slater P. J. 
Published: May 2007

AbstractWe consider probabilistic graphs G = (V, E) in which each edge xy ∈ E fails independently with probability q. The reliability measure studied is pair‐connectivity, the expected number of pairs of connected vertices. We examine how the coefficients of the pair‐connected reliability polynomial are determined by the subgraph structure of G, and we use these results to show that in most cases there does not exist a uniformly optimal n‐vertex, m‐edge graph.
Fault‐tolerant extensions of star networks
Authors: Dawson Robert J. , Farrag Abdel Aziz 
Published: May 2007

AbstractAdvances in computer technology have made the construction of complex networks with many processors economically feasible. Because of the complexity of such networks, reliability has become a major concern. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. To achieve this fault‐tolerance capability, some spare processors and interconnection links need to be added. In this case, when some of the basic components of the network fail, their tasks can be dynamically transferred to the spare components and the network can continue to operate. The three main criteria that it is desirable to minimize in a fault‐tolerant design are the number of nodes (processors), the number of edges (links), and the maximum number of connections to a node. Minimizing these attributes is important in practice, as it is unlikely that unbounded increase in the number of nodes, edges, or connections per node would be acceptable in a real design. In this paper, we shall consider this optimization problem when the (nonredundant) network under consideration is organized as a star. We study all possible variations of the problem under the assumption that minimizing nodes has the highest priority.
Minimal diameter double‐loop networks. I. Large infinite optimal families
Authors: Tzvieli Dvora 
Published: May 2007

AbstractDouble‐loop networks G(n,h) (also known as circulants) are considered, where each node i in a loop of n nodes is also joined by chords to the nodes i ± h mod n. An integer n, a hop h, and a network G(n,h) are defined as optimal if the diameter D of G(n,h) equals the lower bound k when n is in R[k] = {2k2 − 2k + 2, …, 2k2 + 2k + 1}. n ∈ R[k], h, and G(n,h) are defined as suboptimal if D = k + 1. New infinite families of optimal networks are identified, along with corresponding optimal hops. For each k, those families contain O(√k) values of the 4k values of n in R[k]. Also, lower and upper bounds on optimal and suboptimal hops are given, along with a simple algorithm to compute those hops whenever they exist. It is conjectured that all values of n are either optimal or suboptimal. The optimal graphs G(n,h) are applicable in the design of ILLIAC‐type interconnection networks for parallel processing and of local area communication networks with minimal transmission delay.
Maximum independent number for series‐parallel networks
Authors: Hsu Lih‐Hsing , Wang Shih‐Yih 
Published: May 2007

AbstractA series‐parallel network is used as a model of electric circuits. Usually, we use a series‐parallel graph to represent a series‐parallel network. However, there are a lot of different graph representations for a single series‐parallel network. For a given graph, a subset of V(G) is called an independent set if there are no edge of G joining two vertices in S. An independent set S of G is maximum if G has no independent set S′ with |S′| > |S|. The number of vertices in a maximum independent set of G is called the independent number of G and is denoted by α(G). The maximum independent number α(N) for a series‐parallel network N is defined to be the maximum α(G[N]) among all possible graph representations G[N]. In this paper, we are going to present a linear time algorithm to compute α(N) for any series‐parallel network N.
Computational development of a lagrangian dual approach for quadratic networks
Authors: Ventura Jose A. 
Published: May 2007

AbstractA Lagrangian dual approach for large‐scale quadratic programs due to Lin and Pang is adapted to the quadratic cost network flow problem. The unconstrained dual problem is solved iteratively by combining conjugate gradient directions withfiniteline‐search methods. By exploiting the graph structure, matrix and vector operations are streamlined so that the technique can be used for large problems. A computational study of randomly generated networks with up to 500 nodes and 20,000 arcs gives a comparison between combinations of different conjugate direction formulas with three line‐search techniques. The results demonstrate the clear superiority of the Polak‐Ribiere direction formula combined with a variant of a line‐search technique originally developed by Bitran and Hax for convex knapsack problems.
On dependence and reliability computations
Authors: Egeland Thore , Huseby Arne Bang 
Published: May 2007

AbstractWhen computing the reliability of a system consisting of several components, it is usually assumed that the components are statistically independent of each other. In case the components are associated, it is known that this leads to underestimation if the system is a series, whereas the converse holds for parallel systems. In this paper, we consider general monotone systems and study the error resulting from the independence assumption when the component states are, in fact, distributed according to certain dependence models. We also consider some applications of the results to network systems.
Solution properties of oligopolistic network equilibria
Authors: Qiu Yuping 
Published: May 2007

AbstractIn this article, we consider an oligopolistic market equilibrium problem defined on a bipartite network with suppliers on one side and demand regions on the other. With certain reasonable conditions on the supply and demand functions, we shall first show that the equilibrium solution exists and is unique and then show that this equilibrium solution is also Lipschitz continuous and directionally differentiable with respect to smooth perturbations.
Computing rooted communication reliability in an almost acyclic digraph
Authors: Hagstrom Jane Nichols 
Published: May 2007

AbstractThis article considers the reliability problem of computing the probability that the root‐vertex of a directed network can communicate with all other vertices of the network when arcs are subject to random failure. Ball and Provan have observed that when the network contains no directed cycles this probability can be computed in linear time. This paper considers the problem when the network is almost acyclic, that is, when the number of simple directed cycles in the network is small. A new algorithm for computing network reliability is presented. The algorithm is based on expressing the reliability in terms of the derivative of the network reliability with respect to the reliability of an arc. Given a class of networks with a fixed number of simple cycles c, the computation requirements of the new algorithm are O(|E|c+1), where |E| is the number of arcs. Comparison of coded versions of this algorithm and one of Ball's as well as theoretical comparison with one of Buzacott's confirm that this algorithm is to be preferred when the number of directed cycles is small in comparison to the number of vertices.
The cut cone, L1 embeddability, complexity, and multicommodity flows
Authors: Avis David , Deza Michel 
Published: May 2007

AbstractA finite metric (or more properly semimetric) on n points is a nonnegative vector d = (dij) 1 ⩽ i < j ⩽ n that satisfies the triangle inequality dij ⩽ dik + djk. The L1 (or Manhattan) distance ‖x − y‖1 between two vectors x = (xi) and y = (yi) in Rm is given by ‖x − y‖1 = ∑1⩽i⩽m |xi − yi|. A metric d is L1‐embeddable if there exist vectors z1, z2,…, zn in Rm for some m, such that dij = ‖zi − zj‖1 for 1 ⩽ i < j ⩽ n. A cut metric is a metric with all distances zero or one and corresponds to the incidence vector of a cut in the complete graph on n vertices. The cut cone Hn is the convex cone formed by taking all nonnegative combinations of cut metrics. It is easily shown that a metric is L1‐embeddable if and only if it is contained in the cut cone. In this expository paper, we provide a unified setting for describing a number of results related to L1‐embeddability and the cut cone. We collect and describe results on the facial structure of the cut cone and the complexity of testing the L1‐embeddability of a metric. One of the main sections of the paper describes the role of L1‐embeddability in the feasibility problem for multi‐commodity flows. The Ford and Fulkerson theorem for the existence of a single commodity flow can be restated as an inequality that must be valid for all cut metrics. A more general result, known as the Japanese theorem, gives a condition for the existence of a multicommodity flow. This theorem gives an inequality that must be satisfied by all metrics. For multicommodity flows involving a small number of terminals, it is known that the condition of the Japanese theorem can be replaced with one of the Ford–Fulkerson type. We review these results and show that the existence of such Ford–Fulkerson‐type conditions for flows with few terminals depends critically on the fact that certain metrics are L1‐embeddable.
Solving multistage stochastic networks: An application of scenario aggregation
Authors: Mulvey John M. , Vladimirou Hercules 
Published: May 2007

AbstractThe scenario aggregation algorithm is specialized for stochastic networks. The algorithm determines a solution that does not depend on hindsight and accounts for the uncertain environment depicted by a number of appropriately weighted scenarios. The solution procedure decomposes the stochastic program to its constituent scenario subproblems, thus preserving the network structure. Computational results are reported demonstrating the algorithm's convergence behavior. Acceleration schemes are discussed along with termination criteria. The algorithm's potential for execution on parallel multiprocessors is discussed.
Maximum flows in probabilistic networks
Authors: Nagamochi Hiroshi , Ibaraki Toshihide 
Published: May 2007

AbstractThe reliability of capacitated networks subject to random arc failures is evaluated by the expected value of maximum flow. It is known that calculating the expected value of maximum flow is NP‐hard, but a lower bound can be efficiently computed by the method of Carey and Hendrickson. This bound sometimes gives the exact value, e.g., if graphs are bipartite. In this article, for directed and undirected networks, respectively, we give necessary and sufficient conditions for the above lower bound to provide the exact value.
Balanced spanning forests and trees
Authors: Ali Agha Iqbal , Huang Chung‐Hsing 
Published: May 2007

AbstractThis work addresses spanning forests and trees in which the number of nodes in component subtrees is balanced. The solution procedure developed makes use of Lagrangean relaxation and heuristics. Dual‐ascent procedures in conjunction with heuristics are used to yield lower and upper bounds. Computational experience indicates that optimal or suboptimal solutions with very tight bounds can be obtained in 180 to 300 iterations on the average for 100‐node balanced tree problems and 700 to 1400 iterations for 100‐node balanced forest problems.
Approximate solutions of capacitated fixed‐charge minimum cost network flow problems
Authors: Khang Do Ba , Fujiwara Okitsugu 
Published: May 2007

AbstractThis article proposes two approximate methods to solve capacitated, single‐commodity and fixed‐charge network flow problems. First, relaxed problems obtained by the Lagrange relaxation method are shown to form a minimum spanning tree problem, yielding a lower bound to the original problem. The subgradient optimization technique can be then applied to improve this bound by updating the Lagrange multipliers. The second part of the article presents a new, simple, and efficient heuristic to find a feasible and approximate solution that is also an upper bound to the original problem.
A primal‐dual algorithm for the minimum average weighted length circuit problem
Authors: Yang Chengen , Jin Dayong 
Published: May 2007

AbstractWe present a primal‐dual algorithm for solving the minimum average weighted length circuit problem. The algorithm solves the problem by solving a series of subproblems with more combinatorial aspects iteratively. We also prove that the complexity of the algorithm is O(n4 max{tij}) and show that our algorithm is actually a generalization of the Karp–Orlin algorithm. Finally, the relationship between the two algorithms is discussed.
Sensitivity analysis of 0‐1 multiterminal network flows
Authors: Lin Shiow C. , Ma Eva 
Published: May 2007

AbstractGiven an undirected 0‐1 flow network G with n nodes, Gomory and Hu's algorithm solves the multiterminal maximum flow problem by constructing a cut‐tree for G. Their algorithm requires solving n − 1 maximum flow problems. A perturbed network of G is a network generated from G by deleting or adding an edge to G. For a given network G and an edge (s, t) to be deleted from (resp., added to) G, a marginal cut‐tree T is a cut‐tree for G from which a cut‐tree for the perturbed network can be generated easily by reducing (resp., increasing) by 1 the weight of every edge in the path between s and t in T. Given an undirected 0‐1 flow network G, a cut‐tree for G, and an edge to be deleted from or added to G, we present an algorithm to generate a cut‐tree for the perturbed network by first transforming the given cut‐tree for G into a marginal cut‐tree and then transforming the marginal cut‐tree into a cut‐tree for the perturbed network. This algorithm also requires solving the maximum flow problem; depending on the input data, the number of such problems to be solved is between 0 and n − 2 for edge deletion and between 0 and n − 1 for edge addition. Properties on the input data that lead, respectively, to the best‐case and worst‐case complexities of the algorithm are identified, and numerical experiments are included.