Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Finding a Hamiltonian Cycle in a Hierarchical Dual-Net with Base Network of p -Ary q -Cube
verfasst von : Yamin Li, Shietung Peng, Wanming Chu
Erschienen in: Algorithms and Architectures for Parallel Processing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We first introduce a flexible interconnection network, called the hierarchical dual-net (HDN), with low node degree and short diameter for constructing a large-scale supercomputer. The HDN is constructed based on a symmetric product graph (base network). A
k
-level hierarchical dual-net, HDN(
B
,
k
,
S
), contains
${(2N_0)^{2^k}/(2\prod_{i=1}^{k}s_i)}$
nodes, where
S
= {
s
i
|1 ≤
i
≤
k
} is the set of integers with each
s
i
representing the number of nodes in a super-node at the level
i
for 1 ≤
i
≤
k
, and
N
0
is the number of nodes in the base network
B
. The node degree of HDN(
B
,
k
,
S
) is
d
0
+
k
, where
d
0
is the node degree of the base network. The benefit of the HDN is that we can select suitable
s
i
to control the growing speed of the number of nodes for constructing a supercomputer of the desired scale. Then we show that an HDN with the base network of
p
-ary
q
-cube is Hamiltonian and give an efficient algorithm for finding a Hamiltonian cycle in such hierarchical dual-nets.