Note: |
|
(LaTeX) 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. |
URL for the Abstract: |
|
Categories,
Keywords: |
Categories and Subject Descriptors: F.I.2 [Computation by Abstract Devices]: Modes of Computation-- alternation and nondeterminism, F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerieal Algorithms and Problems--computations on discrete structures, F.2.3 [Analysis of Algolithms and Problem Complexity]: Trade-offs among Complexity Measures, G.2 2 [Discrete Mathematics]: Graph Theory General Terms: Algorithms, Theory
Additional Key Words and Phrases: Graph embeddings, dilation-cost, expansion-cost, cost trade-offs, generic graphs |
HyperLinks / References / URLs: |
http://portal.acm.org/citation.cfm?doid=2157.322401 |
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Public |
|