Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  On crossing numbers of hypercubes and cube connected cycles

Sýkora, O., & Vrto, I.(1991). On crossing numbers of hypercubes and cube connected cycles (MPI-I-91-124). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

 

einblenden: alle

Basisdaten

ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B05C-B Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-002D-92E3-B
Genre: Bericht

Dateien

ausblenden: Dateien
:
91-124.pdf (beliebiger Volltext), 10MB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/11858/00-001M-0000-002D-92E4-9
Name:
91-124.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

ausblenden:
 Urheber:
Sýkora, Ondrej1, Autor
Vrto, Imrich1, Autor
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

ausblenden:
Schlagwörter: -
 Zusammenfassung: Recently the hypercube-like networks have received considerable attention in the field of parallel computing due to its high potential for system availability and parallel execution of algorithms. The crossing number ${\rm cr}(G)$ of a graph $G$ is defined as the least number of crossings of its edges when $G$ is drawn in a plane. Crossing numbers naturally appear in the fabrication of VLSI circuit and provide a good area lower bound argument in VLSI complexity theory. According to the survey paper of Harary et al., all that is known on the exact values of an n-dimensional hypercube ${\rm cr}(Q_n)$ is ${\rm cr}(Q_3)=0, {\rm cr}(Q_4)=8$ and ${\rm cr}(Q_5)\le 56.$ We prove the following tight bounds on ${\rm cr}(Q_n)$ and ${\rm cr}(CCC_n)$: \[ \frac{4^n}{20} - (n+1)2^{n-2} < {\rm cr}(Q_n) < \frac{4^n}{6} -n^22^{n-3} \] \[ \frac{4^n}{20} - 3(n+1)2^{n-2} < {\rm cr}(CCC_n) < \frac{4^n}{6} + 3n^22^{n-3}. \] Our lower bounds on ${\rm cr}(Q_n)$ and ${\rm cr}(CCC_n)$ give immediately alternative proofs that the area complexity of {\it hypercube} and $CCC$ computers realized on VLSI circuits is $A=\Omega (4^n)$

Details

ausblenden:
Sprache(n): eng - English
 Datum: 1991
 Publikationsstatus: Erschienen
 Seiten: 6 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-91-124
BibTex Citekey: SykoraVrto91a
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -