The search functionality is under construction.

Author Search Result

[Author] Jywe-Fei FANG(1hit)

1-1hit
  • Linear Layout of the Supercube

    Jywe-Fei FANG  

     
    PAPER-Network

      Vol:
    E89-D No:2
      Page(s):
    779-782

    In this paper, we study the layout problem of the supercube by embedding-in-book technique. The supercube, a generalization of the hypercube, can be constructed for an arbitrary system size. Moreover, it has the same diameter and connectivity of the corresponding hypercube. Embedding a graph in book is to place nodes along the spine of the book and to draw the edges such that edges residing in a page do not cross. An n-dimensional hypercube is regular because the degree of each node is n. The corresponding supercube with N nodes, where 2n-1 < N 2n and N ≠ 32n-2, is irregular because the degree of each node ranges from 2n - 2 to n - 1. Although Chung et al. have shown that an n-dimensional hypercube can be embedded with n - 1 pages, to lay out the supercube remains a challenging problem owing to its higher degree and irregular structure. In this paper, we show that a supercube of N nodes, where 2n-1 < N 2n, can also be embedded with n - 1 pages and book width N - 2n-2 for 2n-1 < N < 32n-2, and 2n-1 for 32n-2 N 2n.