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):

Bilardi, Gianfranco
Chaudhuri, Shiva
Dubhashi, Devdatt
Mehlhorn, Kurt

dblp
dblp
dblp
dblp

Not MPG Author(s):

?

BibTeX cite key*:

Mehlhorn94e

Title

Title*:

A lower bound for area-universal graphs

Journal

Journal Title*:

Information Processing Letters

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:


Vol, No, pp, Date

Volume*:

51

Number:

2

Publishing Date:

1994

Pages*:

101-105

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We establish a lower bound on the efficiency of rea--universal circuits. The area A u of every graph H that can host any graph G of area (at most) A with dilation d, and congestion c p A= log log A satisfies the tradeoff A u = OmegaGamma A log A=(c 2 log(2d))): In particular, if A u = O(A) then max(c; d) = OmegaGamma p log A= log log A). 1 Introduction Bay and Bilardi [2] showed that there is a graph H which can be laid out in area O(A) and into which any graph G of area at most A can be embedded with load 1, and dilation and congestion O(log A). As a consequence, they showed the existence of an area O(A) VLSI circuit that can simulate any area A circuit with a slowdown of O(log A). This note explores the feasibility of more efficient embeddings. Our main result is Theorem 5 which establishes a limitation relating the area of a universal graph to the parameters of the embedding. Informally, it asserts that any circuit which is universal for a family of graphs of area A, a...

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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{Mehlhorn94e,
AUTHOR = {Bilardi, Gianfranco and Chaudhuri, Shiva and Dubhashi, Devdatt and Mehlhorn, Kurt},
TITLE = {A lower bound for area-universal graphs},
JOURNAL = {Information Processing Letters},
PUBLISHER = {Elsevier},
YEAR = {1994},
NUMBER = {2},
VOLUME = {51},
PAGES = {101--105},
ADDRESS = {Amsterdam, The Netherlands},
}


Entry last modified by Anja Becker, 01/02/2008
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/05/2005 01:57:41 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel

Edit Dates
02.01.2008 14:49:52
05.08.2005 14:24:10
05.08.2005 13:59:00