Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A lower bound for area-universal graphs

Bilardi, G., Chaudhuri, S., Dubhashi, D., & Mehlhorn, K. (1994). A lower bound for area-universal graphs. Information Processing Letters, 51, 101-105.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD3C-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD3D-4
Genre: Zeitschriftenartikel

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Mehlhorn108.pdf (Verlagsversion), 525KB
 
Datei-Permalink:
-
Name:
Mehlhorn108.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bilardi, Gianfranco1, Autor
Chaudhuri, Shiva2, Autor           
Dubhashi, Devdatt1, Autor
Mehlhorn, Kurt2, Autor           
Affiliations:
1Max Planck Society, ou_persistent13              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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...

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-01-021994
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 344509
Anderer: Local-ID: C1256428004B93B8-D4180F9759AD181EC12570540041B4CC-Mehlhorn94e
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information Processing Letters
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 51 Artikelnummer: - Start- / Endseite: 101 - 105 Identifikator: -