bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimal communication in networks with randomly distributed byzantine faults
Authors: Blough Douglas M. , Pelc Andrzej
Published: May 2007

We consider the problem of efficient information exchange in a communication network whose nodes and/or links are subject to Byzantine faults that are randomly and independently distributed through the network. The goal is almost safe communication, i.e., getting to every fault‐free node information about every other fault‐free node, with probability converging to one as the number of nodes grows. We present nonadaptive almost‐safe communication schemes working for various networks in asymptotically optimal time and using an asymptotically optimal number of message bits.
Locating an obnoxious facility on a euclidean network to minimize neighborhood damage
Authors: Sung Chang Sup , Joo Cheol Min
Published: May 2007

This paper considers the problem of locating an obnoxious facility on a Euclidean network that could inflict damage within a λ distance of its location point. The objective is to find a location point that minimizes the sum of weights within the circle of radius λ centered at the location point, where each weight (assigned to a point on the network) represents a numerical scale that typically signifies the extent of the undesirability (or the damage cost) due to the facility located near the weighted point. The weights are assumed discretely distributed over all the nodes but uniformly distributed on all the links of the network. In the problem analysis, some optimal solution properties are found, e.g., the objective function is lower semicontinuous piecewise concave and there is at least one optimal location point in a finite set of candidate points. Using these properties, an efficient solution algorithm is derived and tested with several numerical problems. © 1994 by John Wiley & Sons, Inc.
Weighted k‐cardinality trees: Complexity and polyhedral structure
Authors: Fischetti Matteo , Hamacher Horst W. , Jørnsten Kurt , Maffioli Francesco
Published: May 2007

We consider the k‐CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil‐field leasing and facility layout. Although the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k‐CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex hull of the integer solutions is studied. © 1994 by John Wiley & Sons, Inc.
A new characterization of tree medians with applications to distributed sorting
Authors: Gerstel O. , Zaks S.
Published: May 2007

A new characterization of tree medians is presented: We show that a vertex m is a median of a tree T with n vertices iff there exists a partition of the vertex set into [n/2] disjoint pairs (excluding m when n is odd), such that all the paths connecting the two vertices in any of the pairs pass through m. We show that in this case the sum of the distances between these pairs of vertices is the largest possible among all such partitions, and we use this fact to discuss lower bounds on the message complexity of the distributed sorting problem. We show that, given a network of a tree topology, choosing a median and then routing all the information through it is the best possible strategy, in terms of worst‐case number of messages sent during any execution of any distributed sorting algorithm. We also discuss the implications for networks of a general topology and for the distributed ranking problem. © 1994 by John Wiley & Sons, Inc.
Use of continuous approximations within discrete algorithms for routing vehicles: Experimental results and interpretation
Authors: Hall Randolph W. , Du Yafeng , Lin Julia
Published: May 2007

This paper creates and tests a vehicle routing heuristic that combines features of continuous space modeling and discrete modeling. The goals of the paper were (1) to determine whether exploiting continuous space approximations in the formation of an initial partition of customers into districts produces significant improvements in solution quality and (2) to test the validity of Daganzo's route‐length approximation in cases where shipment sizes are either identical or variable. The initial partition is created by dividing the service region into multiple annuli and then partitioning the annuli with a modified sweep algorithm. The initial solution is iteratively updated with a generalized assignment algorithm, which employs a new method for approximating the cost of inserting a stop into a tour. Computational tests have been systematically performed on over 500 sample problems with up to 170 stops and 70 districts. Unlike prior research, sample problems are sufficiently large to exhibit the multiple‐annuli phenomenon studied in Daganzo's work. Results show that continuous space models can provide substantial improvements in the initial customer partition compared to single‐annulus methods. However, after repeated application of a generalized assignment algorithm, the initial advantage of the continuous space solution tends to evaporate. Results also show that Daganzo's model provides accurate predictions of average distance between stops, especially on large problems with identical shipment sizes. © 1994 by John Wiley & Sons, Inc.
A fast algorithm for bounded generalized processing networks
Authors: Fuller J. David , Lan B.
Published: May 2007

A bounded generalized processing network model has the structure of a cost‐minimizing generalized network, with additional side constraints that, for flows on some arcs, place upper and lower bounds that are proportional to flows on other arcs. We propose and test a heuristic algorithm that takes advantage of the near‐network structure by solving a sequence of generalized network LPs whose data are adjusted in a manner suggested by the solution at previous steps. The algorithm extends an earlier algorithm to achieve better solutions, at the cost of more computing effort. In tests, the algorithm is much faster than is application of the general purpose linear programming code MINOS, and the speed advantage increases with problem size: The algorithm is 27 times faster than MINOS on the largest test problem. The algorithm almost always obtains solutions within 0.05% of the optimum. The proportionality constraints are relaxed in the algorithm, yet the solutions to the test problems satisfy the proportionality constraints to within, at worst, 0.25% of the given proportionality limits. © 1994 John Wiley & Sons, Inc.
An efficient graph planarization two‐phase heuristic
Authors: Goldschmidt Olivier , Takvorian Alexan
Published: May 2007

Given a graph G = (V, E), the graph planarization problem is to find a largest subset F of E, such that H = (V, F) is planar. It is known to be NP‐complete. This problem is of interest in automatic graph drawing, in facilities layout, and in the design of printed circuit boards and integrated circuits. We present a two‐phase heuristic for solving the planarization problem. The first phase devises a clever ordering of the vertices of the graph on a single line and the second phase tries to find the maximal number of nonintersecting edges that can be drawn above or below this line. Extensive empirical results show that this heuristic outperforms its competitors. © 1994 by John Wiley & Sons, Inc.
Forwarding indices of consistent routings and their complexity
Authors: Heydemann M. C. , Meyer J. C. , Sotteau D. , Opatrny J.
Published: May 2007

For a given connected graph G of order n, a routing R is a set of n(n ‐ 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex‐forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge‐forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex‐forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP‐complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge‐forwarding index. © 1994 John Wiley & Sons, Inc.
Sharper analysis of packet routing on a butterfly
Authors: Krishna Arvind , Hajek Bruce , Pietracaprina Andrea
Published: May 2007

We present an algorithm that does packet routing on an N‐node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. We simplify the algorithm by focusing on packet routing and prove bounds on its performance for the cases of permutation routing and uniform, random traffic. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. The simplifications made to Ranade's original algorithm and a more careful analysis enabled us to achieve better constants, which, to the best of our knowledge, are the best to date. © 1994 by John Wiley & Sons, Inc.
Minimal‐distance routing for KYKLOS II
Authors: Du Ding‐Zhu , Hwang F. K. , Odlyzko A. M. , Zhang Yanjung
Published: May 2007

We propose a new routing strategy for the KYKLOS II multiprocessor interconnection network that achieves minimum distance for the path between any two processors. For KYKLOS II with 2n processors, the average distance is shorter than those of previous routing strategies by approximately 2 log2n. The traffic density, a measure of traffic concentration, is better than previous strategies for up to 2000 processors, though asymptotically inferior to a strategy proposed by Jenevein and Menezes. © 1994 by John Wiley & Sons, Inc.
Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
Authors: Xue Jue
Published: May 2007

In this paper, we present a polynomial algorithm that finds an edge‐maximal triangulated subgraph of an arbitrary graph. Then, we use this algorithm as a heuristic for the maximum (weight) clique problem. Finally, a local search routine is incorporated into our heuristic. Computational results comparing our algorithm with two existing edge‐maximal triangulated subgraph algorithms in the literature show that the subgraphs found by our algorithm tend to contain more edges as well as a better clique of the original graph. Computational results comparing our heuristic with other heuristics, including an efficient randomized heuristic, also show the promise of our heuristic. © 1994 by John Wiley & Sons, Inc.
Local bipartite turán graphs and graph partitioning
Authors: Lee Jon , Ryan Jennifer
Published: May 2007

Motivated by the NP‐hard problem of finding a minimum‐weight balanced bipartition of an edge‐weighted complete graph, we studied the class of graphs having the same degrees as bipartite Turán graphs. In particular, we established a maximal set of linear equations satisfied by the counts of the possible incidences of 3‐ and 4‐cycles on such graphs. This leads to extremal results that we exploit in a heuristic for the partitioning problem, as well as in the computation of a Lagrangian bound. Preliminary computational results with the heuristic appear to be quite promising. Further results are established linking various adjacency concepts and measures of nonbipartiteness for such graphs. We also demonstrate the potential power of the Lagrangian bound via a family of examples. © 1994 by John Wiley & Sons, Inc.
Stochastic programs over trees with random arc capacities
Authors: Powell Warren B. , Cheung Raymond K.
Published: May 2007

In this paper, we study a special class of stochastic programs where the recourse problem consists of trees with random arc capacities, which we call tree recourse. We develop an efficient procedure to obtain the expected recourse function exactly for single‐stage problems. This procedure is used in a backward recursion to find the exact expected recourse function for multistage trees. We show that for large trees n‐stage networks can be solved more easily than can a single‐stage network with n‐levels. We also show that the expected recourse functions for single‐stage and n‐stage formulations of the same network can be quite similar. Finally, we illustrate the potential of using the tree recourse problems in a more general stochastic network problem. © 1994 by John Wiley & Sons, Inc.
Mengerian properties, hamiltonicity, and claw‐free graphs
Authors: Flandrin E. , Li H.
Published: May 2007

In relation to the Property Pd,m, we define two parameters generalizing the diameter and the independence number of a graph, study their behaviors, and find new conditions depending on those parameters for a claw‐free graph to be Hamiltonian. © 1994 by John Wiley & Sons, Inc.
A degree sequence problem related to network design
Authors: Bienstock Daniel , Günlük Oktay
Published: May 2007

We consider a combinatorial problem arising in the design and operation of lightwave networks. Nodes in such networks are equipped with tunable transmitters and receivers and communication occurs when the frequency of some transmitter is the same as that of a receiver. This technology enables us to update the network topology to respond to changes in traffic patterns. There are two main optimization problems related to this network structure, one being the design of a target graph more suitable to (future) traffic conditions, and the other being the problem of transforming the current network to this target network. This paper discusses the second problem, i.e., the transition phase when the modifications on the current graph are made through a sequence of intermediate connection networks. In particular, we move from one graph to another by swapping two independent edges in the current graph for two other independent edges not in the current graph, so that the union forms a four‐cycle. We characterize the sequence requiring the minimum number of intermediate graphs together with the necessary and sufficient conditions for the existence of such a sequence. We also develop upper and lower bounds on the length of a shortest sequence by formulating an integer program and solving its continuous relaxation to optimality. We also give an efficient algorithm for the case when the intermediate graphs are required to be connected. © 1994 by John Wiley & Sons, Inc.
A delaunay triangulation‐based heuristic for the euclidean steiner problem
Authors: Beasley J. E. , Goffinet F.
Published: May 2007

In this paper, we present a heuristic for the Euclidean Steiner problem. The basis of this heuristic is to use the Delaunay triangulation to generate candidate Steiner vertices and then to remove redundant Steiner vertices via the minimal spanning tree. This basic algorithm is incorporated into a simulated annealing framework. Computational results are given for a number of test problems drawn from the literature. © 1994 by John Wiley & Sons, Inc.
On super i‐connected graphs
Authors: Boland James W. , Ringeisen Richard D.
Published: May 2007

Inclusive connectivity parameters are measures of local connectivity that are natural restrictions of standard graph connectivity and edge connectivity. We examine the i‐connectivity analogs of super‐k and super‐λ graphs. The primary results here concern the graphs G + K2, i.e., the join of an arbitrary graph with K2. We show that G + K2 is super λ1‐connected for every v ϵ V(G) and every edge e ϵ E(G). Using these local results, we show G + Kn, n ⩾ 2, is super λ‐connected. © 1994 by John Wiley & Sons, Inc.
Note: The diameter of edge domination critical graphs
Authors: Paris Matteo
Published: May 2007

The best previous upper bound on the diameter of an edge domination critical graph with domination number γ is 3γ ‐ 5, found in a paper by Fulman. We improve the bound by one and exhibit a class of edge critical graphs with diameter [⅔γ ‐ 1]. © 1994 by John Wiley & Sons, Inc.
Note: Small integral flows need only sparse networks
Authors: Althöfer Ingo
Published: May 2007

Consider a network on n + 1 vertices and two s ‐ t‐flows f and f * of equal value. f * is called a flow spanner of f if f *(e) ⩽ f(e) for every edge e. In this note, we prove that every integral flow f of value n2‐ε (0 ⩽ ε ⩽ 2) has a flow spanner f * that uses at most O(n2‐ε/2) many edges. A sequence of examples shows that this result is asymptotically optimal. © 1994 by John Wiley & Sons, Inc.
A bad submatrix is easy to find
Authors: Swaminathan R. P.
Published: May 2007

A {0, 1}‐matrix is a consecutive 1's matrix, abbreviated C1M, if there exists a path P such that the vertices of P are indexed on the rows of M and the columns of M are the incidence vectors of the vertex‐sets of subpaths of P. In this paper, given a “special” r × c non‐C1M having n 1's, an O(r + c + n) time algorithm is presented to find a “minimal” submatrix that is also a non‐C1M. The motivation for finding such a “bad” submatrix comes from generating suitable cuts while solving traveling salesman problems using a cuttingplane method. © 1994 by John Wiley & Sons, Inc.
Computation of the forwarding index via flows: A note
Authors: de le Vega W. Fernandez , Manoussakis Y.
Published: May 2007

In a given network with n vertices, a routing is defined as a set of n(n − 1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forwarding index of the network is the minimum of the largest load taken over all routings. We show that the problem of determining the value of the forwarding index (respectively, the forwarding index of shortest routings) is an instance of the multicommodity flow problem (respectively, flow with multipliers). Since many very good heuristics or approximation algorithms are known for these flow problems, it follows from our results that all of these methods can be used for calculating the forwarding index. © 1994 by John Wiley & Sons, Inc.
A proof of Boesch's conjecture
Authors: Wang Guifang
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 defined to be the probability that a graph is connected. A well‐defined synthesis problem is to find a graph that maximizes the probability given the number of nodes n, the number of edges e, and edge failure rate p. The problem of a uniformly optimally reliable graph is to find a graph that is optimal for all possible p. The graph studies are attracting more and more attention. Boesch et al. verified the existence of uniformly optimally reliable graphs when e = n, n + 1,n + 2 and given a conjecture for e = n + 3. In this work, a proof of the conjecture is given and it is proved that any min‐mi graph is 2‐connected. © 1994 by John Wiley & Sons, Inc.
Ripples, complements, and substitutes in singly constrained monotropic parametric network flow problems
Authors: Gautier Antoine , Granot Frieda
Published: May 2007

We extend the qualitative theory of sensitivity analysis for minimum‐cost flow problems developed by Granot and Veinott to minimum‐cost flow problems with one additional linear constraint. Two natural extensions of the “less dependent on” partial ordering of the arcs are presented. One is decidable in linear time, whereas the other yields more information but is NP‐complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal‐flow variations as a function of variations in the problem parameters. The theory of substitutes and complements presents necessary and sufficient conditions for optimal‐flow changes to consistently have the same (or the opposite) sign in two given arcs. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc‐flows, and bounds on the rates of changes are discussed. The departure from the pure network structure is shown to have a profound effect on computational issues. Indeed, the complexity of determining substitutes and complements, although linear for the unconstrained (no additional constraint) case, is shown to be NP‐complete in general for the constrained case. However, for all intractable problems, families of cases arise from easily recognizable graph structures which can be computed in linear time. © 1994 by John Wiley & Sons, Inc.
Maximum likelihood genetic sequence reconstruction from oligo content
Authors: Hagstrom Jane N. , Hagstrom Ray , Overbeek Ross , Price Morgan , Schrage Linus
Published: May 2007

One promising technique for determining long genetic sequences is sequencing by oligonucleotide content. This technique involves probing a segment of the unknown multimillion “character” genetic sequence for the presence or absence of known short subsequences. The information obtained from such hybridization experiments may be represented in network form. Network optimization methods may then be applied to identify the most likely forms of the unknown target sequence. © 1994 by John Wiley & Sons, Inc.
Topological properties, communication, and computation on WK‐recursive networks
Authors: Chen Gen‐Huey , Duh Dyi‐Rong
Published: May 2007

Recently, with the support of the CAPRI (Concurrent Architecture and PRogramming environment for highly Integrated system) project, Vecchia and Sanges proposed a new general class of recursively scalable networks, termed WK‐recursive networks, and developed routing and broadcasting algorithms on them. They have also implemented the WK‐recursive networks using VLSI technology. This paper studies WK‐recursive networks by first investigating their topological properties such as diameter, connectivity, and Hamiltonicity. We then develop new and more efficient routing and broadcasting algorithms. Our routing algorithm can guarantee the shortest paths. Our broadcasting algorithm is much simpler and requires fewer extra bits to be transmitted. The broadcasting tree of our broadcasting algorithm is of minimal height (equal to the diameter), and each node receives the message exactly once. Moreover, we show the execution of descend/ ascend algorithms on the WK‐recursive networks using the bitonic sort as an illustrative example. © 1994 by John Wiley & Sons, Inc.
Applications of matching and edge‐coloring algorithms to routing in clos networks
Authors: Carpinelli John D. , Oruc A. Yavuz
Published: May 2007

Rearrangeable Clos networks have been studied in the literature in connection with telephone switching and communication networks. This paper examines the applicability of matching and edge‐coloring in bipartite graphs to the rearrangement problem in these networks. A survey of various matching and edge‐coloring algorithms is given, and these algorithms are evaluated for their suitability and effectiveness. It is shown that no single matching or edge‐coloring algorithm reported in the literature performs well over all Clos networks. It is further shown that the time complexity of the looping algorithm for Beneš networks is at least as good as any routing algorithm that can be obtained from matching or edge‐coloring. © 1994 by John Wiley & Sons, Inc.
New results for the degree/diameter problem
Authors: Dinneen Michael J. , Hafner Paul R.
Published: May 2007

The results of computer searches for large graphs with given (small) degree and diameter are presented. The new graphs are Cayley graphs of semidirect products of cyclic groups and related groups. One fundamental use of our “dense graphs” is in the design of efficient communication network topologies. © 1994 by John Wiley & Sons, Inc.
A network recourse decomposition method for dynamic networks with random arc capacities
Authors: Powell Warren B. , Cheung Raymond K.‐M.
Published: May 2007

We study a class of two‐stage dynamic networks with random arc capacities where the decisions in the first stage must be made before realizing the random quantities in the second stage. The expected total cost of the second stage is a function of the first‐stage decisions, known as the expected recourse function, which is generally intractable. This paper proposes a new method to approximate the expected recourse function as a convex, separable function of the supplies to the second stage. First, the second‐stage network is decomposed using Lagrangian relaxation into tree subproblems whose expected recourse functions are numerically tractable. Subgradient optimization is then used to update the Lagrange multipliers to improve the approximations. Numerical experiments show that this structural decomposition approach can produce high‐quality approximations of the expected recourse functions for large stochastic networks. © 1994 by John Wiley & Sons, Inc.
Personnel shift assignment: Existence conditions and network models
Authors: van den Berg Yeroon , Panton David M.
Published: May 2007

The personnel scheduling problem is known to be a five‐stage process in which the final stage involves the assignment of shifts to the days worked in the schedule. This paper discusses the existence conditions for both continuous and forward rotating shift assignments and heuristic network algorithms for the determination of such assignments. Results generated for a number of test problems demonstrate, first, that the network devised to search for continuous solutions produces these solutions in a high proportion of cases where such solutions are known to exist. Second, for more general problems, the algorithm is shown to be efficient in its ability to generate either continuous or rotating solutions. © 1994 by John Wiley & Sons, Inc.
Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
Authors: Ravada Sivakumar , Sherman Alan T.
Published: May 2007

We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the Geometric Steiner Minimum Tree Problem (GSMT) in Rd for d = 2,3. Our implementations incorporate an improved method for combining the subproblems, and single‐and double‐edge reduction techniques to eliminate unnecessary Steiner points created by the partitioning process. Results show that these refinements are crucial in practice to produce high‐quality results. Moreover, with these refinements, the partitioning algorithm is an effective practical heuristic, which in less time finds solutions roughly comparable with those computed by Smith's Algorithm. The partitioning algorithm depends on a parameter t through which the user can trade off time for solution quality. To solve each of the subproblems of size at most t, we apply Smith's Algorithm, the only other Steiner tree algorithm known for R3 under the Euclidean norm. Using uniformly generated point sets in the d‐cube [0, 100]d, we compare the running time and solution quality for the partitioning algorithm for various values of t against that of Smith's Algorithm applied to the entire input. We also estimate the constant factor in the 1 + O(t−1/d(d‐1)) asymptotic performance bound proven by Kalpakis and Sherman and find that it is less than one. With d = 2 on input sets of 25 points, our sequential implementation with t = 7 typically found within 6 seconds a Steiner tree within 1% of the cost (342) of that computed by Smith's Algorithm in 20 seconds. At t = 13 and using approximately 15 seconds, our sequential implementation typically found Steiner trees within 0.1% of this cost. Similarly, with d = 3 on input sets of 60 points, our distributed implementation with t = 10 typically found within 22 seconds a Steiner tree within 1% of the cost (1059) of that computed by Smith's Algorithm in 200 seconds. At t = 31 and using approximately 108 seconds, our distributed implementation usually found slightly better Steiner trees than did Smith's Algorithm. © 1994 by John Wiley & Sons, Inc.
Reliable distributed diagnosis for multiprocessor systems with random faults
Authors: Berman Piotr , Pelc Andrzej
Published: May 2007

We study a probabilistic setting for distributed fault diagnosis in multiprocessor systems. A system is an undirected graph with nodes representing processors and edges representing communication links. Processors are assumed to fail independently with some probability p. They test their neighbors, and a fault‐free processor has probability 1 − q of discovering a fault of a failed neighbor in an individual test. Subsequently, fault‐free processors attempt to diagnose all the processors of the system with communication based on the test results. During communication, the behavior of faulty processors may be arbitrary (socalled malicious). For every p ≤ ½, q ≤ 1, we construct systems with O(n log n) links in which distributed probabilistic diagnosis can be achieved with probability of correctness at least 1 − n−1. We also show that for some small fixed p and q a similar result holds for the hypercube. On the other hand, we prove that for sufficiently small k, for a system with n processors and kn log n links, the probability of achieving correct diagnosis cannot exceed n−0.5. © 1994 by John Wiley & Sons, Inc.
An exact lower bound on the number of cut‐sets in multigraphs
Authors: Harada Hideaki , Sun Zheng , Nagamochi Hiroshi
Published: May 2007

A cut‐set in an undirected multigraph G is a subset of edges whose removal makes the graph disconnected. Let mi(G) denote the number of all cut‐sets, each of which consists of i edges. In this paper, for any multigraph G with n nodes and e (⩾3n/2) edges, we show that mi(G) with α ⩽ i ⩽ 2(α ‐ γ) ‐ 3, where α = ⌊2e/n⌋ and γ = ⌊2e/n(n ‐ 1)⌋, is greater than or equal to (\documentclass{article}\pagestyle{empty}\begin{document}$ \left({\matrix{ {e - \alpha } \cr {i - \alpha } \cr } } \right) $\end{document})((α + 1)n ‐ 2e) + (\documentclass{article}\pagestyle{empty}\begin{document}$ \matrix{ {e - \alpha - 1} \cr {i - \alpha - 1} \cr } $\end{document})(2e ‐αn). A necessary and sufficient condition for a multigraph G with given n and e to minimize mi(G) for an i with i ⩽ 2(α ‐ γ) ‐ 3 is presented. We also show that there exists a graph such that the lower bound is tight for all i in the range [α, 2(α ‐ γ) ‐ 3]. © 1994 by John Wiley & Sons, Inc.
Sequences of graphical invariants
Authors: Topp Jerzy
Published: May 2007

For a given graphical invariant π, a sequence (ao, a1,…, an) of positive integers is said to be π‐feasible if there exists a graph G with distinguished vertices ν1, ν2,…, νn such that π(G) = ao and π(G −ν1 −ν2 −…−νi) = ai for i = 1, 2,…,n. In this paper, we investigate π‐feasible sequences for the irredundance, domination, and independence numbers of a graph.
Edge‐tenacious networks
Authors: Piazza Barry L. , Robertst Fred S. , Stueckle Sam K.
Published: May 2007

The stability of a (communication or transportation) network composed of (processing) nodes and (communication or transportation) links is of prime importance to network designers. As the network begins losing links or nodes, eventually, there is a loss in its effectiveness. Thus, it is desirable that networks be constructed to be as stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconfiguration of the network after disruption. Many graph theoretical parameters have been used in the past to describe the stability of networks, including the vertex‐connectivity and edge‐connectivity, toughness and edge‐toughness, integrity and edge‐integrity, and tenacity. In this paper, we study the edge‐tenacity of graphs. We will be primarily interested in edge‐tenacious graphs, which can be considered very stable and are somewhat analogous in edge‐tenacity to honest graphs in edge‐integrity. We prove several results about edge‐tenacious graphs as well as find numerous classes of edge‐tenacious graphs.
Multicommodity flows in simple multistage networks
Authors: Elmallah E. S. , Culberson J. C.
Published: May 2007

In this paper, we consider the integral multicommodity flow problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider three‐stage networks. Using existing results on (g, f)‐factors of bipartite graphs, we show sufficient and necessary conditions for the existence of a solution when the network has at most two secondary switches. In contrast, the problem is shown to be NP‐complete if the network has three or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binary n‐cube, and the generalized cube network) as a proper subset. Networks in the new class may have an arbitrary number of stages. Moreover, each stage may contain identical switches of any arbitrary size. The notion of extrastage networks is extended to the new class, and the problem is shown to have polynomial time solutions on r‐stage networks where r = 3 or where each link has a unit capacity and r ≥ 3. The latter result implies an efficient algorithm for deciding admissible permutations on conventional extrastage hypercubic networks. In contrast, we show that the multicommodity flow problem is NP‐complete on extrastage networks, even if r = 6, each link has an integral capacity ≤ 3, and all flow demands are equal.
Lower bounds for the length of test sequences using UIOs
Authors: Rodrigues Marion , Ural Hasan
Published: May 2007

The optimality of the length of a test sequence for a given finite‐state machine can be determined only with respect to the class of test sequences that employ the same number and type of state identification/verification (SIV) sequences and satisfy the same requirements for the starting and terminating states. Given a certain number and type of SIV sequences, we identify three different types of optimality for test sequences: Type11 requires test sequences to begin and end at the initial state; Type1y requires only that test sequences begin at the initial state; and Typexy imposes no requirements whatsoever on the starting and terminating states. Based on these definitions, we investigate the case where Unique Input Output (UIO) sequences are given as SIV sequences and derive lower bounds for the length of test sequences of Type11, Type1y, and Typexy.
Vertex domination‐critical graphs
Authors: Fulman Jason , Hanson Denis , Macgillivray Gary
Published: May 2007

A graph G is vertex domination‐critical if for any vertex v of G the domination number of G ‐ v is less than the domination number of G. If such a graph G has domination number γ, it is called γ‐critical. Brigham et al. studied γ‐critical graphs and posed the following questions: (1) If G is a γ‐critical graph, is |V| ≥ (δ + 1)(γ ‐ 1) + 1?(2) If a γ‐critical graph G has (Δ + 1)(γ ‐ 1) + 1 vertices, is G regular? (3) Does i = γ for all γ‐critical graphs? (4) Let d be the diameter of the γ‐critical graph G. Does d ≤ 2(γ ‐ 1) always hold? We show that the first and third questions have a negative answer and the others have a positive answer.
Sales‐delivery man problems on treelike networks
Authors: Averbakh Igor , Berman Oded
Published: May 2007

Suppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location‐routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O(n log n) or O(n). Multiserver variants of the problem on a tree are proved to be NP‐complete. Some modifications of the problem are also investigated.
Simple heuristics for unit disk graphs
Authors: Marathe M. V. , Breu H. , Hunt H. B. , Ravi S. S. , Rosenkrantz D. J.
Published: May 2007

Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on‐line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular objects.
Thirty‐five‐point rectilinear steiner minimal trees in a day
Authors: Salowe Jeffrey S. , Warme David M.
Published: May 2007

Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for any input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 min. Previous algorithms could only solve 16‐ or 17‐point point problems within the 30 min time bound. Problems involving 35 points can be solved, on average, within a day. Our experiments were run on uniformly distributed data on an integer grid.
A capacity scaling algorithm for the constrained maximum flow problem
Authors: Ahuja Ravindra K. , Orlin James B.
Published: May 2007

The constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more thanD. In this paper, we consider two versions of this problem: (i) when the cost of flow on each arc is a linear function of the amount of flow, and (ii) when the cost of flow is a convex function of the amount of flow. We suggest capacity scaling algorithms that solve both versions of the constrained maximum flow problem in O((m log M) S(n, m)) time, wherenis the number of nodes in the network;m, the number of arcs; M, an upper bound on the largest element in the data: and S(n, m), the time required to solve a shortest path problem with nonnegative arc lengths. Our algorithms are generalizations of the capacity scaling algorithms for the minimum cost flow and convex cost flow problems and illustrate the power of capacity scaling algorithms to solve variants of the minimum cost flow problem in polynomial time.
Threshold reliability of networks with small failure sets
Authors: Ball Michael O. , Hagstrom Jane N. , Provan J. Scott
Published: May 2007

This paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. In each model, the arcs randomly and independently take on two possible states–an “operating” state and a “failed” state–corresponding to two different capacity/task‐time values, and the network is required to maintain a specified “threshold” max‐flow/project‐completion‐time value. In general, this problem is NP‐hard. We address the special case in which the difference between the lower and higher arc lengths is constant for every arc in the network. For these special cases, we show that if the underlying system is 1‐critical, i.e., minimally able to withstand a single component failure, then the probability that the system can maintain the required threshold for the flow and planar project scheduling model is computable in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path or, equivalently, that the set of failed elements in a given partial order comprises a chain in that order. We also show how the basic approach can be used to generate bounds for systems that are “almost critical”.
On reliability evaluation of a capacitated‐flow network in terms of minimal pathsets
Authors: Lin Jsen‐Shung , Jane Chin‐Chia , Yuan John
Published: May 2007

Many real‐world systems such as electric power transmission and distribution systems, transportation systems, and manufacturing systems can be regarded as flow networks whose arcs have independent, finite, and multivalued random capacities. Such a flow network is indeed a multistate system with multistate components and so its reliability for the system demand d, i.e., the probability that the maximal flow is no less than d, can be computed in terms of minimal path vectors to level d (named d‐MPs here). The main objective of this paper was to present a simple algorithm to generate all d‐MPs of such a system for each system capacity level d in terms of minimal pathsets. Analysis of our algorithm and comparison to Xue's algorithm shows that our method has the following advantages: (1) the family of d‐MP candidates that it generates is smaller in size and so d‐MPs can be generated more efficiently, (2) it is expressed more intuitively and so easier to understand, and (3) whenever applied in a series‐parallel case, both algorithms are essentially the same, but in a non series‐parallel case, Xue's algorithm needs the extra work to transform the system into a series‐parallel in advance. Two examples are illustrated to show how all d‐MPs are generated by our algorithm and then the reliability of one example is computed.
A survey of efficient reliability computation using disjoint products approach
Authors: Rai Suresh , Veeraraghavan Malathi , Trivedi Kishor S.
Published: May 2007

Several algorithms have been developed to solve the reliability problem for nonseries‐parallel networks using thesum of disjoint products (SDP)approach. This paper provides a general framework for most of these techniques. It reviews methods that help improve computer time and memory requirements in reliability computation. These parameters are generally used to compare SDP algorithms. We also overview three multiple variable inversion algorithms that result in sum of disjoint products expressions with fewer terms than that of algorithms that use only a single‐variable inversion. One common network is solved for two‐terminal network reliability using each of these algorithms. Finally, we have provided a comparison among these techniques.
On truncated‐newton methods for solving the spatial price equilibrium problem
Authors: Florian M. , Thomas S. J. , Zahar R. V. M.
Published: May 2007

A truncated‐Newton method is applied to the spatial price equilibrium problem and the method is compared with other specialized techniques that exploit the inherent network structure of the problem. Variants of the linear conjugate gradient algorithm for approximately solving the Newton equations are discussed. Numerical results for the truncated‐Newton method are compared with those of a block‐SOR method. Tests indicate that the two approaches are comparable when transportation costs are linear. A truncated‐Newton algorithm is far superior if the transportation costs are nonlinear.
Recognizing small subgraphs
Authors: Sundaram Gopalakrishnan , Skiena Steven S.
Published: May 2007

Although the general problem of subgraph isomorphism is NP‐complete, polynomial‐time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. In this paper, we present general algorithms for fixed‐subgraph isomorphism which improve or unify previous results. In particular, we present an O(nfm) algorithm for recognizing a fixed subgraph H with flower number f within a graph G with n vertices and m edges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizing C5 and small even cycles C2k, k ≥ 3.
Graphs with not too many spanning trees
Authors: Ding Guoli
Published: May 2007

Let 𝒢 be a class of graphs that is closed under taking topological minors. We derive in this paper some necessary and sufficient conditions for the existence of a polynomial p(n) such that t(G) ≤ p(|E(G)|) for all graphs G in 𝒢, where t(G) is the number of spanning trees of G.
The prize collecting traveling salesman problem: II. Polyhedral results
Authors: Balas Egon
Published: May 2007

The task of developing daily schedules for a steel rolling mill has been formulated as a Prize Collecting Traveling Salesman (PCTS) Problem, in which a salesman who gets a prize for every city he visits seeks a minimum‐cost tour including enough cities to collect a required amount of prize money. This paper addresses the facial structure of the PCTS polytope, the convex hull of solutions to the PCTS problem. In an earlier paper, we generalized to the PCTS polytope the subtour elimination inequalities for the Asymmetric Traveling Salesman (ATS) polytope. Here, we give a general method for deriving a facet defining inequality for the PCTS polytope from any facet defining inequality for the ATS polytope. We apply the procedure to several well‐known families of facet inducing inequalities for the ATS polytope: comb, odd CAT, SD, clique tree, and lifted cycle inequalities. We also extend the cloning and clique lifting procedure for the ATS polytope to the PCTS polytope.
Repeated uncoordinated information dissemination by flooding
Authors: Topkis Donald M.
Published: May 2007

A dynamic database in a communications network consists of a set of messages, where a sequence of different versions of each message is generated over time in a repeated and uncoordinated process and where the appearances of the various message versions are distributed among the nodes. The message versions are to be disseminated in the network so that each message version eventually resides at each node. Flooding is a distributed procedure for disseminating message versions. The use of flooding to disseminate repeated and uncoordinated message versions is an integral part of a generic adaptive routing mechanism similar to that used in ARPANET and proposed for the INTERNET and is an element of a method proposed for improving survivability in intra‐LATA networks. A model is formulated to analyze the performance of the dissemination by flooding of repeated and uncoordinated message versions. The worst‐case time complexity is established, showing that flooding is an optimal procedure in terms of this measure. Special properties of flooding in a tree are also established. A key parameter is a separator, which is a lower bound on the time interval between the initial generation of a particular version of any message and the initial generation of the next version of that message.
An improved heuristic for the period vehicle routing problem
Authors: Chao I‐Ming , Golden Bruce L. , Wasil Edward
Published: May 2007

In the period vehicle routing problem, each customer requires a certain number of deliveries per week. Given these frequency requirements, customers must be allocated to days. A vehicle routing problem is solved over each day. We have improved upon best‐known solutions to problems from the literature using a new heuristic procedure. The heuristic also works well on 19 newly generated test problems.
Network upgrading problems
Authors: Paik Doowon , Sahni Sartaj
Published: May 2007

Graphs with weights and delays associated with their edges and/or vertices are often used to model communication and signal flow networks. Network performance can be improved by upgrading the network vertices. Such an upgrade reduces the edge/vertex delays and comes at a cost. We study different formulations of this network performance improvement problem and show that these are NP‐hard. We then consider one of the formulations and develop polynomial time algorithms for some special cases and pseudopolynomial time algorithms for others.