Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

Independent Spanning Trees on Folded Hypercubes

Authors: Jinn-Shyong Yang; Jou-Ming Chang; Hung Chan;

Independent Spanning Trees on Folded Hypercubes

Abstract

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if they are rooted at the same node without sharing any common edge. A folded hypercube is a strengthened variation of hypercube obtained by adding additional links between nodes that are Hamming distance furthest apart. Ho [C.-T. Ho, Full bandwidth communications on folded hypercubes, in Proc. 1990 International conference on Parallel Processing, vol. 1, 1990, pp. 267-280] presented an algorithm for constructing n+1 edge-disjoint spanning trees in an n-dimensional folded hypercube. In this paper, we prove that indeed all spanning trees constructed by this algorithm are independent, i.e., any two spanning trees have the same root, say r, and for any other node $v\ne r$, the two different paths from $v$ to $r$, one path in each tree, are internally node-disjoint.

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    9
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
9
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!