Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We propose two new measures of conditional connectivity to be the extension of Rg-connectivity and Rg-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F(p) + degG–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κg,d,k(λg,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ1,1,k, κ1,d,2, λ1,1,1 and λ1,d,2 for the hypercubes.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
33--45
Opis fizyczny
Bibliogr. 22 poz., rys.
Twórcy
autor
- College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
autor
- School of Computer Science and Technology, Soochow University, Suzhou 215006, China
autor
- School of Computer Science and Technology, Soochow University, Suzhou 215006, China
autor
- Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.
autor
- Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.
Bibliografia
- [1] Abraham S, Padmanabhan K. The twisted cube topology for multiprocessors: a study in networks asymmetry, Parallel and Distributed Computing, 1991;13(1):104-110. URL https://doi.org/10.1016/0743-7315(91)90113-N.
- [2] Chang NW, Hsieh SY. {2, 3}-extraconnectivities of hypercube-like networks, Journal of Computer and System Sciences, 2013;79(5):669-688. URL https://doi.org/10.1016/j.jcss.2013.01.013.
- [3] Chen YC, Tan JJM. Restricted connectivity for three families of interconnection networks, Applied Mathematics and Computation, 2007;188:1848-1855. URL https://doi.org/10.1016/j.amc.2006.11.085.
- [4] Day K, Tripathi A. Unidirectional star graphs, Information Processing Letters, 1993;45:123-129. URL https://doi.org/10.1016/0020-0190(93)90013-Y.
- [5] Efe K. The crossed cube architecture for parallel computation, IEEE Transactions on Parallel and Distributed Systems, 1992;3(5):513-524. URL https://doi.org/10.1109/71.159036.
- [6] Esfahanian AH. Generalized measures of fault tolerance with application to n-cube networks, IEEE Transactions on Computers, 1989;38(11):1586-1591. URL https://doi.org/10.1109/12.42131.
- [7] Esfahanian AH, Hakimi SL. On computing a conditional edge-connectivity of a graph, Information Processing Letters, 1988;27:195-199. URL https://doi.org/10.1016/0020-0190(88)90025-7.
- [8] Fábrega J, Fiol MA. On the extra connectivity of graphs, Discrete Mathematics, 1996;155(13):49-57. URL https://doi.org/10.1016/0012-365X(94)00369-T.
- [9] Harary F. Conditional connecticity, Networks, 1983;13(3):347-357. doi:10.1002/net.3230130303.
- [10] Harary F, Hayes JP, Wu HJ. A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 1988;15:277-289. URL https://doi.org/10.1016/0898-1221(88)90213-1.
- [11] Hong WS, Hsieh SY. Extra edge connectivity of hypercube-like networks, International Journal of Parallel, Emergent and Distributed Systems, 2013;28(2):123-133. URL https://doi.org/10.1080/17445760.2011.650696.
- [12] Hsieh SY, Chang YH. Extraconnectivity of k-ary n-cube networks, Theoretical Computer Science, 2012;443:63-69. URL https://doi.org/10.1016/j.tcs.2012.03.030.
- [13] Hsu LH, Lin CK. Graph Theory and Interconnection Networks, CRC Press, 2008. ISBN-13:9781420044812.
- [14] Ju MY, Wang JJ, Chang SH. Diameter variability of hypercubes, Theoretical Computer Science, 2014;542:63-70. URL https://doi.org/10.1016/j.tcs.2014.04.033.
- [15] Lai PL, Tan JJM, Chang C, Hsu LH. Conditional diagnosability measures for large multiprocessor systems, IEEE Transactions on Computers, 2005;54(2):165-175. doi:10.1109/TC.2005.19.
- [16] Latifi S, Hegde M, Pour MN. Conditional connectivity measures for large multiprocessor systems, IEEE Transactions on Computers, 1994;43(2):218-222. doi:10.1109/12.262126.
- [17] Li XJ, Xu JM. Edge-fault tolerance of hypercube-like networks, Information Processing Letters, 2013;113:760-763. URL https://doi.org/10.1016/j.ipl.2013.07.010.
- [18] Louri A, Sung HK. An optical multi-mesh hypercube: A scalable optical interconnection network for massively parallel computing, Journal of Lightwave Technology, 1994;12(4):704-716. doi:10.1109/50.285368.
- [19] Pai KJ, Chang JM, Yang JS, Wu RY. Incidence coloring on hypercubes, Theoretical Computer Science, 2014;557:59-65. URL https://doi.org/10.1016/j.tcs.2014.08.017.
- [20] Wang YQ. Super restricted edge-connectivity of vertex-transitive graphs, Discrete Mathematics, 2004;289(1-3):199-205. URL https://doi.org/10.1016/j.disc.2004.08.011.
- [21] Yang WH, Meng JX. Extra connectivity of hypercubes, Applied Mathematics Letters, 2009;22(6):887-891. URL https://doi.org/10.1016/j.aml.2008.07.016.
- [22] Zhu Q, Xu JM, Lv M. Edge fault tolerance analysis of a class of interconnection networks, Applied Mathematics and Computation, 2006;172:111-121. URL https://doi.org/10.1016/j.amc.2005.01.126.
Uwagi
Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-5d57a9c6-d4c3-463b-a973-a7fd72045bb6