Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Dilation d Embeddings of a Hyper–Pyramid into a Hypercube
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1989 (English)Conference paper, Published paper (Refereed)
Abstract [en]

A P(k, d) hyper-pyramid is a level structure of k Boolean cubes where the cube at level i is of dimension id, and a node at level i - 1 connects to every node in a d dimensional Boolean subcube at level i, except for the leaf level k. Hyper-pyramids contain pyramids as proper subgraphs. We show that a P(k, d) hyper-pyramid can be embedded in a Boolean cube with minimal expansion and dilation d. The congestion is bounded from above by 2d+1/d+2 and from below by 1 + 2d-d/kd+1. For P(k, 2) hyper-pyramids we present a dilation 2 and congestion 2 embedding. As a corollary a complete n-ary tree can be embedded in a Boolean cube with dilation max(2, log2n) and expansion 2klog2n + 1/nk+1-1/n-1. We also discuss multiple pyramid embeddings.

Place, publisher, year, edition, pages
1989. 294-303 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-65556DOI: 10.1145/76263.76295OAI: oai:DiVA.org:kth-65556DiVA: diva2:483465
Conference
Supercomputing 89
Note
NR 20140805Available from: 2012-01-25 Created: 2012-01-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 45 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf