Paired many-to-many disjoint path covers in restricted hypercube-like graphs

详细信息    查看全文

• 作者：Jung-Heum Park ^{j.h.park@catholic.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Hypercube-like graph ; Disjoint path ; Path cover ; Path partition ; Fault tolerance ; Interconnection network
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：27 June 2016
• 年：2016
• 卷：634
• 期：Complete
• 页码：24-34
• 全文大小：542 K

文摘

Given two disjoint vertex-sets, science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si1.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=d29b79875ad3ae94d90474edb2b97c2f" title="Click to view the MathML source">S={s₁,…,s_k}$S=\{s_1,\dots ,s_k\}$ and science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si2.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=db762580c048386a38fef31639c6aefa" title="Click to view the MathML source">T={t₁,…,t_k}$T=\{t_1,\dots ,t_k\}$ in a graph, a paired many-to-many k-disjoint path cover between S and T   is a set of pairwise vertex-disjoint paths science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si3.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=ba428691c6774dc941749cac21e643ac" title="Click to view the MathML source">{P₁,…,P_k}$\{P_1,\dots ,P_k\}$ that altogether cover every vertex of the graph, in which each path science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si4.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=27e67e78eba5d79c8e42e1859da43ee4" title="Click to view the MathML source">P_i$P_i$ runs from science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si5.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=20ba3eacb5988a69d4c57c645f84ab31" title="Click to view the MathML source">s_i$s_i$ to science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si6.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=4c6adf9e3b7d93b46279ba61255a71a0" title="Click to view the MathML source">t_i$t_i$. A family of hypercube-like interconnection networks, called restricted hypercube-like graphs  , includes most non-bipartite hypercube-like networks found in the literature, such as twisted cubes, crossed cubes, Möbius cubes, recursive circulant science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si7.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=9e1e0e513a28fafd41002b148575db50" title="Click to view the MathML source">G(2^m,4)$G(2^m,4)$ of odd m, etc. In this paper, we show that every m  -dimensional restricted hypercube-like graph, science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si32.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=d051a8fb02408d952e8372289b1d8de8" title="Click to view the MathML source">m≥5$m\ge 5$, with at most f vertex and/or edge faults being removed has a paired many-to-many k-disjoint path cover between arbitrary disjoint sets S and T of size k   each, subject to science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si30.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=382674f1503268cdff15e73bf3bc14fe" title="Click to view the MathML source">k≥2$k\ge 2$ and science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si10.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=d0567e63e4d3fa4ba18303058637d563" title="Click to view the MathML source">f+2k≤m+1$f+2k\le m+1$. The bound science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si11.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=75bf9b7d6f309888ad7666a620b58b05" title="Click to view the MathML source">m+1$m+1$ on science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516300354&_mathId=si12.gif&_user=111111111&_pii=S0304397516300354&_rdoc=1&_issn=03043975&md5=e3c99a320e2b97bc7f6d4b6ffcee59fc" title="Click to view the MathML source">f+2k$f+2k$ is the best possible.