English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The bijective connection graph encompasses a family of cube-based topologies, and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-dimensional bijective connection graphs include the hypercube and almost all of its variants with the order <inline-formula> <tex-math notation="LaTeX">$2^{n}$ </tex-math></inline-formula> and the degree <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. Hence, it is important to design and implement algorithms that work in bijective connection graphs. The set-to-set disjoint paths problem is as follows: given a set of source nodes <inline-formula> <tex-math notation="LaTeX">$S=\{ \boldsymbol s _{1}, \boldsymbol s _{2},\ldots, \boldsymbol s _{p}\}$ </tex-math></inline-formula> and a set of destination nodes <inline-formula> <tex-math notation="LaTeX">$D=\{ \boldsymbol d _{1}, \boldsymbol d _{2},\ldots, \boldsymbol d _{p}\}$ </tex-math></inline-formula> in a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-connected graph <inline-formula> <tex-math notation="LaTeX">$G=(V,E)$ </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">$p\le k$ </tex-math></inline-formula>, construct <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> paths <inline-formula> <tex-math notation="LaTeX">$P_{i}$ </tex-math></inline-formula>: <inline-formula> <tex-math notation="LaTeX">$\boldsymbol s _{i}\leadsto \boldsymbol d _{j_{i}}$ </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">$1\le i\le p$ </tex-math></inline-formula>) such that <inline-formula> <tex-math notation="LaTeX">$\{j_{1},j_{2},\ldots,j_{p}\}=\{1,2,\ldots,p\}$ </tex-math></inline-formula> and the paths <inline-formula> <tex-math notation="LaTeX">$P_{i}$ </tex-math></inline-formula> are node-disjoint. Finding a solution to this problem is an important issue in parallel and distributed computation as well as the node-to-node disjoint paths problem and the node-to-set disjoint paths problem. In this paper we propose an algorithm that constructs <inline-formula> <tex-math notation="LaTeX">$p~(\le n)$ </tex-math></inline-formula> disjoint paths between any pair of node sets in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-dimensional bijective connection graphs in polynomial-order time of <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. We give a proof of correctness of the algorithm as well as the estimates of the time complexity <inline-formula> <tex-math notation="LaTeX">$O(n^{3}p^{4})$ </tex-math></inline-formula> and the maximum path length <inline-formula> <tex-math notation="LaTeX">$n+p-1$ </tex-math></inline-formula>. According to a computer experiment in a locally twisted cube as an example of a bijective connection graph to construct <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> disjoint paths, the average time complexity of the algorithm is <inline-formula> <tex-math notation="LaTeX">$O(n^{2})$ </tex-math></inline-formula>, and the average maximum path is <inline-formula> <tex-math notation="LaTeX">$0.6333n-0.266$ </tex-math></inline-formula>.

Set-to-Set Disjoint Path Routing in Bijective Connection Graphs