hide
Free keywords:
-
Abstract:
An embedding of the graph G in the graph H is a one-to-one association of the
vertices of G with the vertices of H. There are two natural measures of the
cost of a graph embedding, namely, the dilationcost of the embedding: the
maximum distance in H between the images of vertices that are adjacent in G;
and the expansion-cost of the embedding: the ratio of the size of H to the size
of G. The main results of this paper illustrate three situaUons wherein one of
these costs can be minimized only at the expense of a dramatic increase in the
other cost. The first result establishes the following: There is an embedding
of n-node complete ternary trees in complete binary trees with dilation-cost 2
and expansion cost O(n~), where ~ = 1og3(4/3); but any embedding of these
ternary trees in binary trees that has expansion-cost c < 2 must have
dilation-cost G(logloglogn). The second result provides a stronger but less
easily stated example of the same type of trade-off. The third result concerns
generic binary trees, that is, complete binary trees into which all n-node
binary trees are "efficiently" embeddable. There is a generic binary tree into
which all n-node binary trees are embeddable with dilauon-cost O(1) and
expansion-cost O(n ~) for some fixed constant c; if one insists on embeddings
whose dilation-cost is exactly 1, then these embeddings must have
expansion-cost f~(n¢~°*~)/~); tf one insists on embeddmgs whose expansion-cost
is less than 2, then these embeddings must have dilation cost ~(log log log n)
An interesting application of the polynomial size genenc binary tree m the
first part of this three-part result is to yield simplified proofs of several
results concerning computational systems with an intrinsic nouon of
"computation tree," such as alternating and nondeterministic Turing machines
and context-free grammars.
