bluuebunny/crossref_metadata_2025 huggingface dataset:
Centroids to centers in trees
Authors: Reid K. B.
Published: May 2007

If k is a nonnegative integer and x is a vertex of a tree T, the k‐ball branch weight of x, denoted b(x;k), is the number of vertices in a largest subtree of T, all of whose vertices are a distance at least k + 1 from x. The k‐ball branch weight centroid of T, denoted W(T;k), consists of all vertices x of T for which b(x;k) is a minimum. The usual branch weight centroid of T (which is also the median) is W(T;0), and the center of T is W(T;r), where r is the radius of T. In this paper, the structure of the subgraph spanned by W(T;k) is examined. Similarities and differences with Slater's k‐centrum [6] and k‐nucleus [7] are discussed.
Efficient algorithms for inferring evolutionary trees
Authors: Gusfield Dan
Published: May 2007

In this paper, we examine two related problems of inferring the evolutionary history of n objects, either from present characters of the objects or from several partial estimates of their evolutionary history. The first problem is called the Phylogeny problem, and second is the Tree Compatibility problem. Both of these problems are central in algorithmic approaches to the study of evolution and in other problems of historical reconstruction. In this paper, we show that both of these problems can be solved by graph theoretic methods in linear time, which is time optimal, and which is a significant improvement over existing methods.
Shortest path algorithms using dynamic breadth‐first search
Authors: Goldfarb Donald , Hao Jianxiu , Kai Sheng‐Roan
Published: May 2007

A 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

Given 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

Manufacturers 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

This 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

A 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

Let 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

We 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

A 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

We 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

We 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

The 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

We 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

Advances 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

Double‐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.
Uniformly‐most reliable networks do not always exist
Authors: Myrvold Wendy , Cheung Kim H. , Page Lavon B. , Perry Jo Ellen
Published: May 2007

Boesch conjectured that there is always a uniformly‐most reliable graph on n points and e edges. We present an infinite family of counterexamples to this conjecture.
Maximum independent number for series‐parallel networks
Authors: Hsu Lih‐Hsing , Wang Shih‐Yih
Published: May 2007

A 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

A 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

When 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.
A two‐commodity sharing problem on networks
Authors: Ichimori Tetsuo , Katoh Naoki
Published: May 2007

This paper considers a sharing problem of distributing a given quantity of resources to a set of demand nodes in a network as equally as possible. We study the case in which the resources are of two distinct kinds and propose a polynomial time algorithm for it by reducing the problem to the one‐commodity sharing problem.
Solution properties of oligopolistic network equilibria
Authors: Qiu Yuping
Published: May 2007

In 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

This 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

A 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

The 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

The 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

This 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

This 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

We 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

Given 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.
A multiphase approach to the period routing problem
Authors: Russell Robert A. , Gribbin Dave
Published: May 2007

In this article, we present a multiphase approach to the period routing problem. The period routing problem involves the design of effective vehicle routes that satisfy customer service frequencies over a specified planning horizon. The first phase of analysis consists of a generalized network approximation to achieve an efficient initial solution. The second phase involves an interchange heuristic that reduces distribution costs by solving a surrogate traveling salesman problem. The third phase consists of an interchange heuristic that further reduces the distribution costs by addressing the actual vehicle routes of the period routing problem. A fourth phase utilizes a 0–1 integer model to attempt further improvements. Computational results on test problems indicate that the multiphase approach yields improvements over previous best solutions.
Minimum flows in (s,t) planar networks
Authors: Adlakha V. , Gladysz B. , Kamburowski J.
Published: May 2007

The minimum flow problem in a network is to find a flow with the smallest value so that the flow on each arc is bounded from below by the arc capacity. We present a linear time algorithm for solving the problem in (s,t) planar directed networks.
Characterizing stochastic flow networks using the monte carlo method
Authors: Alexopoulos Christos , Fishman George S.
Published: May 2007

Consider a flow network G = (𝒱,ℰ) with node set 𝒱 and arc set ℰ = {1, …, e}. Assume that the nodes do not restrict flow transmission and the arcs have random, discrete and independent capacities B1, …, Be, and let B = {B1, …, Be}. Also, let s and t be a pair of nodes in 𝒱, let Λ(B) denote the value of a maximum s–t flow, and let Γ denote a set of s–t cuts. This work describes a highly efficient Monte Carlo sampling plan for estimating the probability that l < Λ(B) ⩽ u, the probability that a cut in Γ is critical and l < Λ(B) ⩽ u, and the probability that a cut in Γ is critical, given that l < Λ(B) ⩽ u. The proposed method takes advantage of an easily computed upper bound on the probability that l < Λ(B) ⩽ u, which is a function of both l and u to gain its computational advantage. The article also describes techniques for computing confidence intervals that are valid for any sample size. Algorithms for implementing the proposed sampling experiment are included, and an example illustrates the efficiency of the proposed method.
The steiner problem in the hypercube
Authors: Miller Zevi , Perkel Manley
Published: May 2007

Let Q(n) be the n‐dimensional hypercube, and X, a set of points in Q(n). The Steiner problem for the hypercube is to find the smallest possible number L(n,X) of edges in any subtree of Q(n) that spans X. We obtain the following results:

An exact formula for L(n,X), when |X| ≤ 5.

The bound L(n,X) ≤ (nk+1) + (2 + o(1)) ([log (k)]/k)(nk) as k → ∞, when X is the set of all points in Q(n) of a given weight k + 1, provided (k2/[log (k)])1 + 1/k ≤ n.

NP‐completeness of deciding L(n,X) even when every point of X has weight at most 2.
Distance‐constrained multifacility minimax location problems on tree networks
Authors: Erkut E. , Francis R. L. , Tamir A.
Published: May 2007

We consider the problem of locating new facilities with respect to existing facilities on a tree network. The objective is to minimize the maximum of the weighted distances between existing and new facilities and between pairs of new facilities. There are upper bounds on the distances between pairs of new facilities and between new and existing facilities. We give a polynomial order, binary search algorithm, based on rational representation of data. We also present a strongly polynomial order algorithm employing a parameteric approach and exploiting parallelism.
Steiner tree problems
Authors: Hwang F. K. , Richards Dana S.
Published: May 2007

We give a survey up to 1989 on the Steiner tree problems which include the four important cases of euclidean, rectilinear, graphic, phylogenetic and some of their generalizations. We also provide a rather comprehensive and up‐to‐date bibliography which covers more than three hundred items.
The n‐line traveling salesman problem
Authors: Rote Günter
Published: May 2007

The special case of the Euclidean traveling salesman problem, where the n given points lie on a small number (N) of parallel lines in the plane, is solved by a dynamic programming approach in time nN, for fixed N, i.e., in polynomial time. This extends a result of Cutler (1980) for three lines. Such problems arise, for example, in the fabrication of printed circuit boards, where the distance traveled by a laser that drills holes in certain places of the board should be minimized. The parallelity condition can be relaxed to point sets that lie on N “almost parallel” line segments. We give a characterization of the allowed segment configurations by a set of forbidden subconfigurations.
On the optimal strongly connected orientations of city street graphs. III. Three east–west avenues or north–south streets
Authors: Roberts Fred S. , Xu Yonghua
Published: May 2007

We consider strongly connected orientations of the grid graph which has n1 + 1 eastwest avenues and n2 + 1 north–south streets. We seek optimal strongly connected orientations according to several different definitions of optimality. In earlier work, such optimal orientations were found for n1, n2 both at least 4 and for n1 = 1. Here we consider the case n1 = 2.
Financial flow of funds networks
Authors: Nagurney Anna , Hughes Merritt
Published: May 2007

This article develops a general network model of financial flow of funds accounting that explicitly incorporates feedback and can be used to calculate reconciled values of all outstanding financial instruments, tangible assets, and net worth. The model captures, as special cases, distinct data‐specific problem scenarios and permits the estimation of sector holdings of both assets and liabilities, total outstanding instrument volumes, and total sector holdings. A decomposition algorithm is then proposed that resolves the network problem into simpler network subproblems, each of which can then be solved exactly in closed form. The algorithm is applied to a dataset derived from the Federal Reserve Board data for 1989. The reconciled dataset can then be used as a base line for an empirical general equlibrium model and for macromonetary policy analysis.
Optimal routing and process scheduling for a mobile service facility
Authors: Akinc Umit , Srikanth Kizhanatham
Published: May 2007

This paper deals with the problem of delivering a well‐defined service to a given set of points efficiently. Efficiencies are sought through providing the services by use of a mobile service unit (MSU). The service facility is mobile in the sense that it can move from point to point at some “move” cost. Unlike the traveling salesman‐type problems however the present problem does not require a physical visit to every point for servicing. Points can be serviced from a distance, while the facility is stationed at a nearby point, at some “processing” cost that may depend on many factors, including the distance involved. The problem is to find the subset and the sequence of nodes that the mobile service unit should physically visit and the set of other points it should service while at each of these visited nodes so as to minimize the sum of move and processing costs. A Lagrangean‐based branch‐and‐bound algorithm is proposed. This algorithm is aided by a powerful upper‐boundig routine and sensitivity tests and logical dominance rules to fix zero/one variables. Somewhat encouraging computational results are presented.
A routing algorithm for virtual circuit data networks with multiple sessions per O—D pair
Authors: Yee James R. , Lin Frank Y. S.
Published: May 2007

In virtual circuit networks, all the packets in a session are transmitted over exactly one path established between the origin and the destination. For each origin–destination pair, it is assumed that there are multiple sessions. We consider the problem of choosing a path for each session so as to minimize the average packet delay in the network. We formulate this problem as a nonlinear multicommodity flow problem with integer decision variables. An iterative scheme that is similar to local search is developed to solve this problem. In each iteration, we apply Lagrangean relaxation and a multiplier adjustment procedure to solve a restricted problem. We show that the Lagrangean dual problem can be solved exactly by solving a convex program. In computational experiments, our algorithm determines solutions that are within 1% of an optimal solution in minutes of CPU time for networks with 26–61 nodes. In addition, we show that our proposed algorithm is better both theoretically and computationally than K(0)‐ordering, single‐path routing, or round‐off Frank–Wolfe heuristics.
A reliability‐improving graph transformation with applications to network reliability
Authors: Satyanarayana A. , Schoppmann L. , Suffel C. L.
Published: May 2007

This paper considers a probabilistic graph in which the points are perfectly reliable but the edges operate independently of one another, all with some known probability p. The graph G is in an operating state if the surviving edges induce a spanning connected subgraph of G. The all‐terminal reliability R(G,p) of G is the probability that G is in an operating state. A graph transformation, called “the swing surgery,” is introduced, and it is shown that this surgery has important properties. First, if H is the graph obtained by deleting m independent edges from the complete graph, then for any other graph G with the same number of points and edges as H, R(H,p) > R(G,p) for all 0 < p < 1. Moreover, the swing surgery yields a simple topological proof of the well‐known result that H has more spanning trees than does G. Another important consequence is that given any graph G there exists a threshold graph T with the same number of points and edges as G such that R(T,p) ≤ R(G,p) for all 0 < p < 1.
The generalized P‐forest problem on a tree network
Authors: Tamir Arie , Lowe Timothy J.
Published: May 2007

In two recent papers, similar multifacility problems on tree networks were studied where facilities are subtrees of the tree. The complexity of the problems was left as open. In this paper, we formulate a general model that includes the above‐cited problems as special cases and give a polynomial algorithm to solve the general model.
Complexity results for well‐covered graphs
Authors: Sankaranarayana Ramesh S. , Stewart Lorna K.
Published: May 2007

A graph with n vertices is well covered if every maximal independent set is a maximum independent set and very well covered if every maximal independent set has size n/2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well‐covered graph recognition is co‐NP‐complete and that several other problems are NP‐complete for well‐covered graphs. A number of these problems remain NP‐complete on very well covered graphs, while some admit polynomial time solutions for the smaller class. For both families, the isomorphism problem is as hard as general graph isomorphism.
Special cases of traveling salesman and repairman problems with time windows
Authors: Tsitsiklis John N.
Published: May 2007

Consider a complete directed graph in which each arc has a given length. There is a set of jobs, each job i located at some node of the graph, with an associated processing time hi, and whose execution has to start within a presepecified time window [ri, di]. We have a single server that can move on the arcs of the graph, at unit speed, and that has to execute all of the jobs within their respective time windows. We consider the following two problems: (a) minimize the time by which all jobs are executed (traveling salesman problem) and (b) minimize the sum of the waiting times of the jobs (traveling repairman problem). We focus on the following two special cases: (a) The jobs are located on a line and (b) the number of nodes of the graph is bounded by some integer constant B. Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times ri are 0, and (c) all of the deadlines di are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP‐completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time t, the number of jobs that can be executed at that time is bounded.
On a parametric shortest path problem from primal—dual multicommodity network optimization
Authors: Polak George G.
Published: May 2007

Each iteration of the primal—dual linear programming algorithm entails a dual update. For the maximal multicommodity flow problem, and for multicommodity network synthesis, that requires finding a breakpoint in a parametric all pairs' shortest path problem. A procedure based on the Floyd—Warshall Algorithm solves this problem in polynomial (cubic in the number of nodes) time.
The optimal partitioning of networks
Authors: Cheng Chung‐Kuan
Published: May 2007

The work proposes several partitioning criteria, i.e, the flux cutA, the flux cutB, the cost ratio cut, and one generalized minimum cut. The flux cutBis an extension of the flux cutA. The cost ratio cut generates an optimal partitioning for a linear placement problem. The generalized minimum cut uses a cost function related to a polynomial function of the sizes of two partitioned subsets. A high‐order polynomial function tends to generate partitions such that the partitioned subsets equal specified sizes. A simplified case is the ratio cut that is shown to derive the clustering structure of the network. The physical meaning of the cuts is described. The partitioning problems are shown to be strongly related to the communication problems. Several network flow models are constructed. We illustrate relations between the maximum flow solutions and the minimum partitionings. We use linear programming to formulate the proposed maximum flow problems. The duality techniques of linear programming are utilized to derive a relation to the optimal partition solution. Thus, we have identified the cases when the optimal partition solutions can be determined in polynomial time.
Sequential information dissemination by packets
Authors: Bagchi A. , Schmeichel E. F. , Hakimi S. L.
Published: May 2007

Consider a network consisting of units and links that connect pairs of units. Suppose each of the units possesses a unique message that is to be received by all other units. This is called gossiping. A related problem is that of census taking in which a particular unit has to receive every other unit's message. We study gossiping and census taking in a network in which the units communicate by transmitting packets of a fixed size, so that only a bounded number of messages can be sent in a single transmission. We also discuss the complexity of gossiping when the messages are of different sizes.
Paths through a maze of rectangles
Authors: Coffman E. G. , Gilbert E. N.
Published: May 2007

Finding short paths through mazes of rectangles has applications in VLSI wire‐routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst‐case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average‐case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.
Algorithms for K‐terminal reliability problems with node failures
Authors: Elmallah Ehab S.
Published: May 2007

Consider a distributed processing system with a set K of sites that can either cooperate in computing a function or hold resources required by other sites. The system is implemented using a communication network with unreliable nodes. Two simplified reliability problems then arise. In the first problem, we are interested in computing the probability that every operational pair of sites in K can communicate with each other. This problem is known to be #P‐complete. In the second problem, the sites in K are service centers. Our reliability measure is the probability that every operational site in the network is connected to at least one operational service center. In this paper, we define the class of t‐polygon graphs, t ≥ 3, as the intersection graphs of straight‐line chords in a convex t‐gon. Hence, any t‐polygon graph is a circle graph. We show that both problems admit polynomial time solutions when the underlying graph of the network is restricted to a t‐polygon graph, for a fixed t.
Cell suppression: Disclosure protection for sensitive tabular data
Authors: Kelly James P. , Golden Bruce L. , Assad Arjang A.
Published: May 2007

When a statistical agency, such as the United States Bureau of the Census, publishes tabular data, it must withhold certain data elements that contain confidential information associated with the data respondents. Cell suppression is a technique commonly used in the publishing of economic data in tabular formats. The sensitive entries, which are called primary suppressions, need to be suppressed. However, the suppression of the primary cells alone still allows one to estimate a range for each of the missing values by considering the published entries. Additional entries in the table must be suppressed to ensure that these ranges are not too narrow. Traditionally, the protection required is defined by an interval centered around the value of each primary suppression. This paper formulates and develops solution techniques for the traditional problem as well as for a relaxation of the problem where sliding protection ranges are allowed. In the relaxed problem, the protection ranges have fixed widths but are free to slide; the only restriction is that each range must contain the value of the primary suppression. We present network flow‐based heuristics for both versions of the cell suppression problem and use a lower‐bounding procedure to evaluate the performance of the heuristics. Extensive computational results based on real‐world and randomly generated tables demonstrate that sliding protection ranges can significantly reduce the total amount of suppressed data, as compared to the traditional suppression scheme. Furthermore, the heuristics produce optimal or near‐optimal solutions for real‐world problems.
On a leverage problem in the hypercube
Authors: Hamburger Peter , Pippert Raymond E. , Douglas Weakley W.
Published: May 2007

The leverage of a set S of elements (vertices and edges) of a graph G, with respect to a graphical parameter P, is the change induced in P by the removal of S. We consider the case in which G is a hypercube and P is the sum of the distances between vertices. The determination of the minimum leverage of any set of k edges leads to the question of the existence of a perfect matching in which no two edges lie on a 4‐cycle. We give a constructive proof of the existence of such a matching and note additional interesting problems.
Reliable communication in networks with Byzantine link failures
Authors: Pelc Andrzej
Published: May 2007

We consider the problem of communication between nodes of a network whose links are subject to arbitrary failures: A failed link may not only stop transmitting messages but may corrupt them in any possible way. We characterize networks allowing communication in spite of at most t failures. Also, for every fixed link failure probability p ≤ .29, we construct a class of networks for which the probability of successful communication converges to 1 as the number of nodes grows. It is shown that the number of links in these networks is asymptotically smallest possible to assure reliable communication. Moreover, in these networks, communication can be completed in just two information exchange rounds. Finally, we give a protocol assuring reliable communication in the hypercube if link failure probability is p ≤ .02 and show that no such protocol exists if p ≥ .15.
Finding all minimum‐cost perfect matchings in Bipartite graphs
Authors: Fukuda Komei , Matsui Tomomi
Published: May 2007

The Hungarian method is an efficient algorithm for finding a minimal‐cost perfect matching in a weighted bipartite graph. This paper describes an efficient algorithm for finding all minimal‐cost perfect matchings. The computational time required to generate each additional perfect matching is O(n(n + m)), and it requires O(n + m) memory storage. This problem can be solved by algorithms for finding the Kth‐best solution of assignment problems. However, the memory storage required by the known algorithms grows in proportion to K, and, hence, it may grow exponentially in n. So, our specialized algorithm has a considerable advantage in memory requirement over the precious more general algorithms for Kth‐best assignment problems. Here we will show that the enumeration of all minimal‐cost perfect matchings can be reduced to the enumeration of all perfect matchings in some bipartite graph. Therefore, our algorithm can be seen as an algorithm for enumerating all perfect matchings in a given bipartite graph.
Tighter time bounds on fault‐tolerant broadcasting and gossiping
Authors: Gargano Luisa
Published: May 2007

Consider a network in which n processors are connected by unreliable lines and are allowed to communicate with at most one other processor at a time. In this paper, the problems of broadcasting and gossiping are considered. Broadcast is the task of transmitting a message, originated at one node, to all other nodes in the network. Gossiping refers to the process of information dissemination when each processor knows a unique item of information and must transmit it to all the other processors in the network. In this paper, new bounds on fault‐tolerant broadcasting and gossiping times are obtained. The given bounds improve on previously known results. In particular, if n is a power of two, the given broadcast and gossiping schemes require minimum time and are supported by a network having the minimum possible number of edges.