In this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time.

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that theta (n log n+k/sub r/) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k/sub r/ is the number of processor recoveries experienced.>

The authors parallelize the embedding strategy for mapping any two-dimensional grid into its optimal hypercube with minimal dilation. The parallelization allows each hypercube node to independently determine, in constant time, which grid node it will simulate and the communication paths it will take to reach the hypercube nodes that simulate its grid-neighbors. The paths between grid-neighbors are chosen in such a way as to curb the congestion at each hypercube node and across each hypercube edge. Explicity, the node congestion for the embedding is at most 6, one above optimal, while the edge congestion is at most 5.>

The focus is on the following graph-theoretic question associated with the simulation of complete binary trees by faulty hypercubes: if a certain number of nodes or links are removed from an n-cube, will an (n-1)-tree still exists as a subgraph? While the general problem of determining whether a k-tree, k>

The pinwheel is a hard-real-time scheduling problem for scheduling satellite ground stations to service a number of satellites without data loss. Given a multiset of positive integers (instance) A=(a/sub 1/, . . . a/sub n/), the problem is to find an infinite sequence (schedule) of symbols from (1,2, . . . n) such that there is at least one symbol i within any interval of a/sub i/ symbols (slots). Not all instances A can be scheduled; for example, no 'successful' schedule exists for instances whose density is larger than 1. It has been shown that any instance whose density is less than 2/3 can always be scheduled. Two new schedulers are proposed which improve this 2/3 result to a new 0.7 density threshold. These two schedulers can be viewed as a generalization of the previously known schedulers, i.e. they can handle a larger class of pinwheel instances including all instances schedulable by the previously known techniques.>

This paper addresses the following graph-embedding question: given a grid and the smallest hypercube with at least as many nodes as the grid has grid points, how can grid points be assigned to hypercube nodes (with at most one grid point per node) so as to keep grid-neighbors as near each other as possible in the hypercube? For two-dimensional grids, a simple embedding strategy is introduced which ensures that grid-neighbors are always mapped to hypercube nodes that are within a distance of two edges of each other. Moreover, this embedding algorithm takes time linear to the number of grid points. Extending and adding further concepts, an embedding strategy is formulated for d-dimensional grids which ensures that grid-neighbors are distanced by $O(d)$ edges in the hypercube. This algorithm takes $O(d \times {\text{ the number of grid points}})$ time.

The problem of finding Hamiltonian circuits in faulty hypercubes is explored. There are many different Hamiltonian circuits in a nonfaulty hypercube. The question of interest here is the following: if a certain number of links are removed from the hypercube, will a Hamiltonian circuit still exist? In partial answer to this question are the following results. First, it is shown that for any n-cube $( n\geqq 3 )$ with $\leqq 2n - 5$ link faults in which each node is incident to at least two nonfaulty links, there exists a Hamiltonian circuit consisting of only nonfaulty links. Since as will be shown, there exists an n-cube with $2n - 4$ faulty links, in which each node is incident to at least two nonfaulty links, for which there is no Hamiltonian circuit, this result is optimal. Second, it is shown that the problem of determining whether an n-cube with an arbitrary number of link faults has a Hamiltonian circuit is NP-complete.

The following graph-embedding question is addressed: given a two-dimensional grid and the smallest hypercube with at least as many nodes as grid points, how can one assign grid points to hypercube nodes (with at most one grid point per node) so as to keep grid neighbors near each other in the cube? An embedding scheme for an infinite class of two-dimensional grids is given that keeps grid neighbors within a distance of two apart.>