Let \(G\) be a finite graph with vertices \(\xi_1, \ldots, \xi_n\), and let \(S_1, \ldots, S_n\) be disjoint non-empty finite sets. We give a new proof of a theorem characterizing the least possible number of connected components of a graph \(D\) such that \(V(D) = S_1 \cup \cdots \cup S_n\), \(E(D) = E(G)\) and, when an edge \(\lambda\) joins vertices \(\xi_i, \xi_j\) in \(G\), it is required to join some element of \(S_i\) to some element of \(S_j\) in \(D\) (so that, informally, \(D\) arises from \(G\) by splitting each vertex \(\xi_i\) into \(|S_i|\) vertices).

Regular graphs play an important role in designing interconnection networks for multiprocessing systems; but these regular graphs like hypercubes or star graphs cannot be constructed with an arbitrary number of nodes. The purpose of the present paper is to examine two families of almost regular maximally fault tolerant graphs (based on hypercubes and star graphs respectively) that can be defined for an arbitrary number of nodes.

We consider the problem of minimizing total flow time for the imprecise computation model introduced by Lin et al. Leung et al. have shown that the problem of finding a minimum total flow time schedule subject to the constraint that the total error is no more than a given threshold \(K\) is NP-hard, even for a single processor. In this paper we give a fast heuristic for a set of tasks with a large deadline. We show that the heuristic produces schedules with total flow time no more than \({3}/{2}\) times the optimum solution. Examples are given showing that the ratio can asymptotically approach \({3}/{2}\) for a single processor and \({5}/{4}\) for multiprocessors. A second heuristic is given for a single processor and a set of tasks with different deadlines. It is shown that the worst-case performance bound of the heuristic is \(2\) and the bound is tight.

A \(2\)-connected graph is called \(Y – \Delta\) (respectively \(\Delta – Y\)) \({reducible}\) or simply a \(Y – \Delta\) (respectively \(\Delta – Y\)) graph if it can be reduced to a single edge using a sequence of \(Y – \Delta\) (respectively \(\Delta – Y\), series and parallel reductions. This paper addresses the problem of decomposing \(Y – \Delta\) and \(\Delta – Y\) graphs in connection with a new method for decomposing \(3\)-connected graphs proposed recently by Coullard, Gardner, and Wagner.

To determine the error-correcting capability of a large error-correcting code it may be necessary to generate the code, an intractable task. Using a stack-based algorithm and utilizing structural properties of a code can reduce the time required. Timing results are reported for generating large codes using these methods on massively parallel platforms.

Consider a queue of \(N\) customers waiting to purchase an item that costs \(1\) dollar. Of them, \(m\) customers have a \(1\)-dollar bill and \(n\) customers have only a \((1+\mu)\) dollar bill, where \(\mu\) is a positive integer. The latter need to get change in the amount of \(\mu\) dollars. If at the time of their service, the cashier has less than \(\mu\) \(1\)-dollar bills, they have to wait for change according to some queue discipline. It is assumed that the cashier has no initial change, and that all the queue arrangements are equi-probable. Using transformations of lattice graphs, we derive the probability distribution of the number of customers who will have to wait for change under a queue discipline that corresponds to the ballot problem. Limiting results and other applications are also given.

A simple new proof of an existence condition for periodic complementary binary sequences is given. In addition, this result is extended to the general case, which was previously unsolved.

Token-passing algorithms are a well-known way of solving distributed mutual exclusion problems in computer networks. A simple abstraction of the concept of tokens allows the use of elementary constructions in general hypergraphs to show that certain sets of tokens are minimal. This suggests other problems about hypergraphs worthy of exploration. As an application, we introduce a new mutual exclusion problem, the \({Excluded \; Taxpayer \; Problem}\), which requires exponentially many tokens even though it can be solved in linear time by other methods.