Abstract One of Frank Boesch's best known papers is ‘The strongest monotone degree condition for n‐connectedness of a graph’ (Boesch, J Combinatorial Theory Ser B 16 (1974), 162–165.). In this article, we give a simple sufficient degree condition for a graph to be k‐edge‐connected, and also give the strongest monotone condition for a graph to be 2‐edge‐connected. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We begin by examining the dynamic behavior of a facility location such as a 1-median or a 1-center on a network when the parameters of the network are known functions of time. The parameters of the network include the lengths of the edges and the demands at the nodes. In our formulation, time is considered a discrete variable and it is assumed that the facility can only serve customers while it is stationary and that the demands at time t are fully satisfied before time t + 1. In particular, if x(t) denotes the location of the facility for t = 1, 2, … , the cost would be the sum of the costs of satisfying the demands at the various times plus the cost of moving the facility along its route implied by x(t). We also examine certain path (route) selection problems in dynamic networks. Recent past literature is surveyed. Various extensions including the multifacility versions of the above problems are studied. © 1999 John Wiley & Sons, Inc. Networks 34: 250–257, 1999

It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the problem of orienting a connected graph with cut edges in order to maximize the number of ordered vertex pairs (x, y) such that there is a directed path from x to y. After transforming this problem, we prove a key theorem about the transformed problem that allows us to obtain a quadratic algorithm for the original orientation problem. We also consider how to orient graphs to minimize the number of ordered vertex pairs joined by a directed path. After showing this problem is equivalent to the comparability graph completion problem, we show both problems are NP-hard, and even NP-hard to approximate to within a factor of 1 + ε, for some ε > 0.

We study the problem of locating replicas of a database on a network to minimize the communication cost. We first present extensions of the p-median theorem to prove that under two different measures of communication cost one can always optimally locate the replicas at the vertices (nodes) of the network. We briefly review the fact that the problem is NP-hard for general networks under either measure of communication cost, and we then provide efficient algorithms for solving the problem on tree networks for either of the two measures. © 1997 John Wiley & Sons, Inc. Networks 30:31–36, 1997

The problem of broadcasting long messages on store-and-forward communication networks, where a processor (node) can send and receive messages simultaneously to and from all its neighbors, was studied by Bermond and Fraigniaud. In such networks, the delays encountered by a message from a node v to all other nodes over a broadcast spanning tree is directly proportional to the length of the paths in the tree over which the message is sent. Furthermore, the speed of the broadcast can be improved by the segmentation of the message at v into equal-length segments and then the broadcast of these segments over arc-disjoint broadcast spanning trees simultaneously. These observations lead Bermond and Fraigniaud to look for the maximum number of arc-disjoint spanning trees in a deBruijn network rooted at an arbitrary node with small depths. This paper improves and extends the results of the above authors.

Each vertex of an undirected graph possesses a piece of information that must be sent to every other vertex. They communicate by sending bounded size packets of messages from one vertex to another. The authors describe parallel algorithms, which accomplish the desired tasks for six prominent architectures. The algorithms are optimal, or nearly so, in every case.

Consider a network consisting of units connected by links in which some units could be faulty. Suppose each unit has a message which must be transmitted to all other (fault-free) units. We present an algorithm for doing this in a network operating in a fully distributed manner that requires at most 3n logn+O(n) message transmissions by fault-free units. Among other things, our result can be used to devise an algorithm for distributed system level diagnosis which is more efficient than the best currently known algorithm for this purpose.>

Abstract The study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (≥1) such facilities. We will consider “center”, “median”, “max eccentricity”, and “max distance sum” location type problems for p = 1 or p > 1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whether a facility is path‐shaped or tree‐shaped. These cases lead to 64 problems. We will determine the algorithmic complexity of virtually all these problems. We conclude with a result that may be viewed as a generalization of the p‐Median theorem. © 1993 by John Wiley & Sons, Inc.

This paper considers the following problem: Given a positive integer t and graph H, construct a graph G from H by adding a minimum number $\Delta ( t,H )$ (respectively, $\Delta ' ( t,H )$) of edges and an appropriate number of vertices, such that after removing any t vertices (respectively, t edges) from G the remaining graph contains H as a subgraph. This problem was motivated by the design of fault-tolerant interconnection networks for multiprocessor systems. The authors estimate $\Delta ( t,H )$ and $\Delta ' ( t,H )$ for the cycle, path, complete binary tree, grid, torus, and hypercube on n vertices.

Consider a network in which each unit initially knows only its own identity and the identity of its immediate neighbors. Suppose each unit has a message intended for all other units. The authors give a distributed algorithm to accomplish this in point-to-point networks which is optimal in the number of transmissions it requires. They also show that this algorithm accomplishes this efficiently for broadcast (radio) networks, although the problem of finding a solution with the least number of transmissions, in broadcast networks, is shown to be NP-hard.>

Given a network N(V, E) and a set of points Xp = {x1, …, xp} on N, we first present an algorithm for computing the Voronoi partition of N(V, E) into territories T(x1), …, T(xp). After describing two ways to measure the “size” of a territory, we introduce and discuss the more challenging problem of selecting Xp so that the maximum size among the resulting territories is as small as possible. For one especially natural way to measure the size of a territory, we show that this latter problem is NP-complete when p is part of the input, but that the problem can be solved in polynomial time for any fixed p. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

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

One of the main methods for designing data link protocols in broadcast networks is based on the allocation of transmission rights to nodes in timeslots guaranteeing collision-free access to the channel. Extensions of certain results on vertex coloring are used to establish bounds on the number of timeslots required for a network to finish transmitting a backlog of data. Such networks are also observed when they are structured as rings and trees. Distributed algorithms for the allocation of timeslots in these networks are presented.>

The one-layer wiring problem of providing a one-to-one connection between two sets of terminals that lie on two horizontal lines by means of wires that are in the forms of disjoint rectilinear curves on a unit grid (where one unit is the minimum spacing between two wires), is called the river routing problem. The problem has been widely studied. Here this problem is studied when the number of horizontal segments in each wire is at most 2, and provide an $0(n^3 )$ time dynamic programming algorithm for finding the minimum separation between the two horizontal lines for n wires.

The vertex arboricity$a(G)$ of a graph G is the minimum number of subsets into which the vertices of G can be partitioned so that each subset induces an acyclic graph. A characterization of planar graphs G is given for which $a(G) = 2$, thereby answering a question of Grünbaum [Israel J. Math., 14 (1973), pp. 390–408]. The characterization is in terms of the dual graph $G^* $. As a corollary, a theorem of Stein that characterizes maximal planar graphs G with $a(G) = 2$ is obtained. This latter result implies that determining whether $a(G)\leqq 2$ is NP-complete for maximal planar graphs G.

T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s ( G ) of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether s ( G ) ≤ K , for a given integer K , is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs G with s ( G ) ≤ K for K = 1, 2, 3.

Abstract The scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.

The problem of how a user incapable of performing tests can diagnose a system, given the results of the Kuhl and Reddy algorithm, (1980 (3 paper), 1981), is addressed. In particular, the authors provide optimal or near-optimal algorithms for this purpose under a variety of assumptions.>

Abstract The scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.

The scheduling of file transfers in networks to minimize the overall finishing time was studied by Coffman, et al. where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver. They first presented complexity results under various conditions. Then they showed that the general problem is NP-complete and provided approximation algorithms. This paper first presents more efficient approximation algorithms with better performances than the above authors’ algorithms for the cases of trees and multitrees. Furthermore, there are simple distributed implementations of our approximation algorithms. Then this paper provides a polynomial time algorithm for finding an optimum schedule for an odd cycle, whose complexity was left as an open question by the above authors.

A class of communication networks which is suitable for "multiple processor systems" was studied by Pradhan and Reddy. The underlying graph (to be called Shift and Replace graph or SRG) is based on DeBruijn digraphs and is a function of two parameters r and m. Pradhan and Reddy have shown that the node-connectivity of SRG is at least r. The same authors give a routing algorithm which generally requires 2m hops if the number of node failures is ≤(r -1). In this paper we show that the node-connectivity of SRG is (2r - 2). This would immediately imply that the system can tolerate up to (2r - 3) node failures. We then present routing methods for situations with a certain number of node failures. When this number is ≤(r - 2) our routing algorithm requires at most m + 3 + logr m hops if 3 + logr m ≤m. When the number of node failures is ≤(2r - 3) our routing algorithm requires at most m + 5 + logr m hops if 4 + logr m ≤ m. In all the other situations our routing algorithm requires no more than 2m hops. The routing algorithms are shown to be computationally efficient.

Abstract In this paper methods are described that will compute the edge‐connectivity of a graph or a digraph at least twice as fast as the known methods. A study of the computation of the vertex‐connectivity is presented which leads to new algorithms for this purpose or for the purpose of determining if the vertex‐connectivity is at least k. These algorithms compare favorably with Kleitman's, Even's, Even and Tarjan's, and Galil's algorithms.

In the theory of t-fault-diagnosable systems, one first chooses a set of diagnostic tests, then seeks the results of these tests, and finally proceeds to use the test results to identify the faulty units assuming that the number of faulty units does not exceed t. Nakajima was the first to suggest a departure from this practice. He proposed to adaptively choose the tests and to seek their results until one can identify a fault-free unit. This fault-free unit may then be used as a tester to identify all faulty units. In this paper, we exploit this idea fully and show that one needs the results of at most (n + 2t −2) adaptive tests to identify all faulty units in a t-fault-diagnosable system with n units. The impact of the applications of this idea to the various models and diagnosis algorithms is examined.

Suppose that n independent tasks are to be scheduled without preemption on an unlimited number of parallel machines of two types: inexpensive slow machines and expensive fast machines. Each task requires a given processing time on a slow machine or a given smaller processing time on a fast machine. We make two different feasibility assumptions: (a) each task has a specified processing interval, the length of which is equal to the processing time on a slow machine; (b) each task has a specified starting time. For either problem type, we wish to find a feasible schedule of minimum total machine cost. It is shown that both problems are NP-hard in the strong sense. These results are complemented by polynomial algorithms for some special cases.

T. Parsons proposed and partially analyzed the following pursuit-evasion problem on graphs: A team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s(G) of searchers that will suffice for guaranteeing capture of the fugitive? We show that determining whether s(G) ≤ K, for a given integer K, is NP-hard for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs with s(G) ≤ K for K = 1,2,3.

This paper begins by giving a characterization of t1/ t1—diagnosable systems. Then a class of t0-diagnosable systems, denoted by d(n,t0,X), is considered. It is shown for any member of this class that: 1) necessary and sufficient conditions for t1/t1—diagnosability are greatly simplified, 2) optimal diagnosis algorithms of time complexity 0(nt0) exist, and most importantly, 3) given the test results, any set F of faults with |F| ≤ t1 can be identified to within a set F' with F ⊆ F' and |F'| ≤ min {t1, |F| + 1}.

Certain graph theoretic problems dealing with the testing of structured programs are treated. A structured digraph is a digraph that represents a structured program. A labelling procedure which characterizes structured digraphs is described. An efficient algorithm for finding a minimum path cover for the vertices of digraphs that belong to an important family of structured digraphs is given. To model interactions among code segments the notions of `required pairs' and `must pairs' are introduced and the corresponding constrained path cover problems are shown to be NP-complete even for acyclic structured digraphs.

It is shown that the problem of finding a codeword with least weight and whose weight is not a multiple ofkin a binary linear code belongs to the class of "nondeterministic polynomial (NP)-hard" problems for anyk\geq 2. Some other related problems are shown to belong to the same class. These results were motivated by a conjecture due to Berlekamp, McEliece, and van Tilborg that the problem of finding the Hamming distance of a code is NP-hard.

In this paper various path cover problems, arising in program testing, are discussed. Dilworth's theorem for acyclic digraphs is generalized. Two methods for fmding a minimum set of paths (minimum path cover) that covers the vertices (or the edges) of a digraph are given. To model interactions among code segments, the notions of required pairs and required paths are introduced. It is shown that rmding a minimum path cover for a set of required pairs is NP-hard. An efficient algorithm is given for findng a minimum path cover for a set of required paths. Other constrained path problems are contsidered and their complexities are discussed.

Dr. H. Fujiwara of Osaka University, Osaka, Japan, has brought to our attention two errors in the above paper.1

This paper is concerned with automatic fault diagnosis for digital systems with multiple faults. Three problems are treated: 1) Probabilistic fault diagnosis is presented using the graph-theoretic model of Preparata et al. The necessary and sufficient conditions to correctly diagnose any fault set whose probability of occurrence is greater than t have been developed. Some simple sufficient conditions are also discussed. 2) A general model that contains as special cases both the graph-theoretic and the Russell-Kime models is developed. Conditions for T-fault diagnosability are given, thus settling some open problems introduced by Russell and Kime. 3) Finally, sequential T-fault diagnosability is considered. Existence of a class of systems requiring as little as n + T - 1 tests is shown. This improves significantly upon the previously best known class of systems that required n + 2T - 2 tests for sequential T-fault diagnosability.

Preparata, Metze, and Chien [1] gave necessary conditions for identification of all faulty units in a system S capable of automatic fault diagnosis. We show that these conditions are sufficient if in S no two units test each other. Necessary and sufficient conditions are also obtained for the general case when no such restriction is placed on S.

Abstract This paper is concerned with construction of graphs, with n vertices and m edges, whose connectivity r = [2m/n] ≧ 3, and have no more than n minimum vertex cut‐sets. Frank's results imply that this is an important step in the design of a class of reliable networks.

Abstract A graph theoretic version of Steiner's problem in plane geometry is described. An approach for solving this problem, related to Melzak's solution to Steiner's problem, is presented. The problems of finding “shortest route” and “minimal spanning tree” in graphs become special cases of the Steiner's problem in graphs. It is shown that a solution to this problem also provides us with a solution to the problems of finding a minimum externally stable set and a maximum internally stable set in a graph.

This correspondence formulatesGF(q)matrix descriptions for a class of weighted, directed graphs. As a result of this formulation, the concept of graph theoretic error-correcting codes is generalized to theq-ary case. It is shown that graph theoreticq-ary codes are completely orthogonalizable and, hence, one-step majority decodable. It is also seen that known techniques for the augmentation of circuit codes can he extended to theq-ary case. The resulting codes remain easily decodable.

It is shown that directed graphs can be used to generate a class of moderately efficient error-correcting codes, which are easily decodable.

A study of the efficiency, error-correcting capabilities, and limitations of graph theoretic block codes is presented. Augmentation of graph theoretic codes and their generation is discussed. It is shown that such augmentation techniques can substantially increase the level of efficiency of these codes and potentially could increase it to the level of the best available codes. Furthermore, the augmented graph theoretic codes are shown to be easily decodable.