We describe novel methods for embedding 2-dimensional grid graphs into cylinders (one way wrap-around grids), tori, and hypercubes, where the guest grid G is larger than the host graph H, implying a many to one embedding. We call $\lceil\mid G\mid / \mid H\mid\rceil$ the optimal load, denoted l. We consider optimal embeddings with respect to dilation (the stretching of guest edges) and load; i.e., edges are mapped to edges or onto one node, and the number of grid nodes mapped onto any hypercube node is not greater than l. We show, by construction, that, for loads of at least 4, optimal embeddings into the hypercube always exist subject only to modest restrictions on the relative dimensions of guest and host. If the problem instances are grouped by grid height, the restrictions imply that only some finite number of instances in each group may not be solvable by the given methods. The essence of the method is a mapping from grids into cylinders of height at least one half of but not greater than the grid height, and so it can also be used to construct embeddings into cylinders and tori. Previous work has gone so far as to show that if the optimal load l is a power of 2, then dilation 1, load l+1 embeddings into the hypercube can be constructed. Optimal results for loads 2 and 3 are not known.

We introduce a novel approach to the classical problem of in-situ, stable merging, where "in-situ" means the use of no more than O(log 2 n) bits of extra memory for lists of size n. Shufflemerge reduces the merging problem to the problem of realising the "perfect shuffle" permutation, that is, the exact interleaving of two, equal length lists. The algorithm is recursive, using a logarithmic number of variables, and so does not use absolutely minimum storage, i.e., a fixed number of variables. A simple method of realising the perfect shuffle uses one extra bit per element, and so is not in-situ. We show that the perfect shuffle can be attained using absolutely minimum storage and in linear time, at the expense of doubling the number of moves, relative to the simple method. We note that there is a worst case for Shufflemerge requiring time\\Omega\\Gamma n log n), where n is the sum of the lengths of the input lists. We also present an analysis of a variant of Shufflemerge which uses a ...

We return to the problem of embedding 2-dimensional (h × w) guest grid graphs into 2-dimensional (h′ × w′) host grid graphs, where w′ < w, and h′ is the smallest integer such that hw ≤ h′w′. This 2-dimensional problem has many applications in computer science including the simulation of one grid of processors by another of different shape. Also, it can likely be applied to more complex problems such as those involving grids of higher dimension and hypercubes. It is already known that optimal dilation, namely two, is always obtainable whenever w/w′, the compression ratio, is no greater than two. Only a restricted set of problem instances with compression ratios greater than two could previously be solved optimally, with respect to dilation. We introduce two new techniques, called folding with compression and folding with extension. By applying folding with compression, we show that optimal solutions always exist if w′ ≥ 7h and the remainder of h′ integer divided by h is no greater than h′ integer divided by h. This condition includes all instances of the problem for which w/w′ ≥ h ≥ 7, i.e., all instances for which the compression ratio and h are sufficiently large. There remain instances, among those of intermediate compression ratio, for which we still do not have optimal solutions. We show that some, but not all, of these can be solved by appling folding with extension. © 1996 John Wiley & Sons, Inc.

It is shown that two-dimensional rectangular grids of large aspect ratio can be embedded into rectangular grids of smaller aspect ratios with small expansion and dilation. In particular, width can be reduced by a factor of up to two with optimal expansion, i.e. when the host rectangle is the smallest sufficient to contain the guest, and optimal dilation, i.e., two. A width reduction factor of three can be obtained with optimal expansion and dilation three. In general, any rectangular grid can be embedded into a square grid that is no more than unity larger on the side than the minimum possible, with dilation no more than three. These results improve on those previously obtained, in which dilation of better than 18 could not be guaranteed. They might be applicable to more complex grid embedding problems, such as embedding multidimensional grids into hypercubes.>

The authors address the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant alpha such that all problems in the family are solvable in time O(n/sup alpha /). The question is modeled by considering a class of polynomially indexed relations. The main results show that (1) this setting supports notions of completeness that can be used to explain the apparent hardness of certain problems with respect to fixed-parameter tractability, and (2) some natural problems are complete.>

It is known that for some NP-complete problem, most instances of the problem can be solved in polynomial time. The classic graph colouring problem is an example for which Monte Carlo algorithms have been given. These algorithms always terminate in polynomial time, and almost always give the correct result. That is to say, as the size of the correct result. That is to say, as the size of the graph tends to infinity, the probability of the algorithm giving a wrong answer on a random graph tends to zero. Here we describe a Las Vegas algorithm for the same problem. This kind of algorithm always gives the correct result and almost always terminates in polynomial time. The algorithm is based on a traversal of a Zykov tree derived from the graph and uses results previously obtained for a Monte Carlo algorithm for the same problem.