English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
EndNote (UTF-8)
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  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

 

show all

Basic

hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B05C-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-002D-92E3-B
Genre: Report

Files

hide Files
:
91-124.pdf (Any fulltext), 10MB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-002D-92E4-9
Name:
91-124.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

hide
 Creators:
Sýkora, Ondrej1, Author
Vrto, Imrich1, Author
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

hide
Free keywords: -
 Abstract: 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

hide
Language(s): eng - English
 Dates: 1991
 Publication Status: Issued
 Pages: 6 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-91-124
BibTex Citekey: SykoraVrto91a
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -