Hilfe Wegweiser Impressum Kontakt Einloggen





Cost Trade-offs in Graph Embeddings, with Applications


Hong,  Jia-Wei
Max Planck Society;

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Rosenberg,  Arnold L.
Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Hong, J.-W., Mehlhorn, K., & Rosenberg, A. L. (1983). Cost Trade-offs in Graph Embeddings, with Applications. Journal of the ACM, 30, 709-728.

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.