Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Hong, Jia-Wei
Mehlhorn, Kurt
Rosenberg, Arnold L.

dblp
dblp
dblp



BibTeX cite key*:

mehlhorn83f

Title

Title*:

Cost Trade-offs in Graph Embeddings, with Applications


Mehlhorn_a_1983_f.pdf (1068.89 KB)

Journal

Journal Title*:

Journal of the ACM

Journal's URL:


Download URL
for the article:

http://delivery.acm.org/10.1145/330000/322401/p709-hong.pdf?key1=322401&key2=4453903611&coll=GUIDE&dl=GUIDE&CFID=4178030&CFTOKEN=30107455

Language:

English

Publisher

Publisher's
Name:

ACM

Publisher's URL:


Publisher's
Address:

New York, USA

ISSN:


Vol, No, pp, Date

Volume*:

30

Number:

4

Publishing Date:

1983

Pages*:

709-728

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

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

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{mehlhorn83f,
AUTHOR = {Hong, Jia-Wei and Mehlhorn, Kurt and Rosenberg, Arnold L.},
TITLE = {Cost Trade-offs in Graph Embeddings, with Applications},
JOURNAL = {Journal of the ACM},
PUBLISHER = {ACM},
YEAR = {1983},
NUMBER = {4},
VOLUME = {30},
PAGES = {709--728},
ADDRESS = {New York, USA},
}


Entry last modified by Christine Kiesel, 11/09/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
08/06/2006 06:42:02 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel

Edit Dates
09.11.2006 18:42:26
12.09.2006 09:49:42
06.08.2006 18:44:10

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_1983_f.pdf
View attachments here: