Author name cluster

M.S. Paterson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2000 Journal Article

Dense edge-disjoint embedding of complete binary trees in interconnection networks

S. Ravindran
A.M. Gibbons
M.S. Paterson

We describe dense edge-disjoint embeddings of the complete binary tree with n leaves in the following n-node communication networks: the hypercube, the de Bruijn and shuffle-exchange networks and the two-dimensional mesh. For the mesh and the shuffle-exchange graphs each edge is regarded as two parallel (or anti-parallel) edges. The embeddings have the following properties: paths of the tree are mapped onto edge-disjoint paths of the host graph and at most two tree nodes (just one of which is a leaf) are mapped onto each host node. We prove that the maximum distance from a leaf to the root of the tree is asymptotically as short as possible in all host graphs except in the case of the shuffle-exchange, in which case we conjecture that it is as short as possible. The embeddings facilitate efficient implementation of many P-RAM algorithms on these networks.

Details DOI

I&C Journal 1991 Journal Article

Planar acyclic computation

W.F. McColl
M.S. Paterson
B.H. Bowditch

This paper considers the following problem: given a specification consisting of a set of variables X, a multiset of functions F on those variables, and a cyclic ordering on X ⌣ F, determine whether or not there exists a planar acyclic circuit which realizes the specification. An algorithm is given which produces such a circuit whenever one exists. In proving that our algorithm meets this requirement we provide some simple mathematical characterizations of those specifications which are realizable.

Details DOI

TCS Journal 1980 Journal Article

Selection and sorting with limited storage

J.I. Munro
M.S. Paterson

When selecting from, or sorting, a file stored on a read-only tape and the internal storage is rather limited, several passes of the input tape may be required. We study the relation between the amount of internal storage available and the number of passes required to select the Kth highest of N inputs. We show, for example, that to find the median in two passes requires at least ω(N 1 2 ) and at most O(N 1 2 log N) internal storage. For probabilistic methods, θ(N 1 2 ) internal storage is necessary and sufficient for a single pass method which finds the median with arbitrarily high probability.

Details DOI

TCS Journal 1976 Journal Article

Circuit size is nonlinear in depth

M.S. Paterson
L.G. Valiant

Two fundamental complexity measures for a Boolean function f are its circuit depth d(f) and its circuit size c(f). It is shown that c≳ 1 4 d·log 2d for all f.

Details DOI