Completely independent spanning trees (CISTs) are a critical mechanism for ensuring reliable communication in interconnection networks. They achieve fault tolerance by providing multiple disjoint paths between any two distinct nodes in the network. However, determining the existence of CISTs in arbitrary networks has been proven to be NP-hard, even when the number of CISTs is as few as two. The generalized hypercube network is an interconnection network structure with excellent topological properties. It not only encompasses classic interconnection networks such as hypercube and k-ary n-cube as special cases, but also serves as the foundational architecture for numerous high-performance data center networks, including BCube, FBFLY, HyperX, and SWCube. This study first proves that there exist <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7843_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\lfloor \frac{n}{2}\rfloor$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation> CISTs in the k-dimensional generalized hypercube <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7843_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="136" /> </InlineMediaObject> <EquationSource Format="TEX">$G(m_1,m_2,\ldots ,m_k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="false">(</mo> <msub> <mi>m</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>m</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>m</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7843_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="193" /> </InlineMediaObject> <EquationSource Format="TEX">$n=\max \{m_1,m_2,\ldots ,m_k\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <msub> <mi>m</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>m</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>m</mi> <mi>k</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. Building on this result, an algorithm is proposed to construct these <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7843_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\lfloor \frac{n}{2}\rfloor$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation> CISTs in the generalized hypercube, providing an effective solution for reliable fault tolerance.

Constructing completely independent spanning trees in the generalized hypercube network

期刊论文
发表日期：

2025年9月23日

查看全文

Hui Dong,
Huaqun Wang,
Mengjie Lv,
Weibei Fan

摘要

Completely independent spanning trees (CISTs) are a critical mechanism for ensuring reliable communication in interconnection networks. They achieve fault tolerance by providing multiple disjoint paths between any two distinct nodes in the network. However, determining the existence of CISTs in arbitrary networks has been proven to be NP-hard, even when the number of CISTs is as few as two. The generalized hypercube network is an interconnection network structure with excellent topological properties. It not only encompasses classic interconnection networks such as hypercube and k-ary n-cube as special cases, but also serves as the foundational architecture for numerous high-performance data center networks, including BCube, FBFLY, HyperX, and SWCube. This study first proves that there exist $\lfloor \frac{n}{2}\rfloor$ $⌊ \frac{n}{2} ⌋$ CISTs in the k-dimensional generalized hypercube $G(m_1,m_2,\ldots ,m_k)$ $G (m_{1}, m_{2}, \dots, m_{k})$ , where $n=\max \{m_1,m_2,\ldots ,m_k\}$ $n = max {m_{1}, m_{2}, \dots, m_{k}}$ . Building on this result, an algorithm is proposed to construct these $\lfloor \frac{n}{2}\rfloor$ $⌊ \frac{n}{2} ⌋$ CISTs in the generalized hypercube, providing an effective solution for reliable fault tolerance.