›› 2015, Vol. 30 ›› Issue (5): 1154-1160.doi: 10.1007/s11390-015-1551-0

Special Issue: Theory and Algorithms

• Regular Paper • Previous Articles    

Constructing Edge-Colored Graph for Heterogeneous Networks

Rui Hou1(侯睿), Student Member, IEEE, Ji-Gang Wu1,2*(武继刚), Member, CCF, IEEEYawen Chen3(陈亚文), Haibo Zhang3(张海波), Xiu-Feng Sui2(隋秀峰), Member, CCF, IEEE   

  1. 1 School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China;
    2 State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;
    3 Department of Computer Science, University of Otago, Dunedin 9054, New Zealand
  • Received:2014-05-24 Revised:2014-11-08 Online:2015-09-05 Published:2015-09-05
  • Contact: Ji-Gang Wu E-mail:asjgwu@gmail.com
  • About author:Rui Hou received his Bachelor's degree in software engineering from Tianjin Polytechnic University (TJPU), Tianjin, in 2012. He is working toward his Master's degree in computer science and technology at the School of Computer Science and Software Engineering in TJPU. His research interests include graph theory, parallel/distributed computing, cluster/grid/cloud computing, optical wireless communication, and high-performance computer architectures.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61173032 and 61202062, the National Natural Science Foundation of China (Tianyuan Special Foundation) under Grant Nos. 11326211 and 11326198, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20131201110002, and the Key Laboratory of Computer Architecture Opening Topic Fund Subsidization under Grant No. CARCH201303.

In order to build a fault-tolerant network, heterogeneous facilities are arranged in the network to prevent homogeneous faults from causing serious damage. This paper uses edge-colored graph to investigate the features of a network topology which is survivable after a set of homogeneous devices malfunction. We propose an approach to designing such networks under arbitrary parameters. We also show that the proposed approach can be used to optimize inter-router connections in network-on-chip to reduce the additional consumption of energy and time delay.

[1] Wang Y, Desmedt Y. Edge-colored graphs with applications to homogeneous faults. Information Processing Letters, 2011, 111(13):634-641.

[2] Wang Y. LT codes for efficient and reliable distributed storage systems revisited. arXiv:1207.5542, 2012. http://arxiv.org/abs/1207.5542, Feb. 2015.

[3] Wang Y. Array BP-XOR codes for reliable cloud storage systems. In Proc. ISIT, Jul. 2013, pp.326-330.

[4] Tan S, Lv J. Characterizing the effect of population heterogeneity on evolutionary dynamics on complex networks. Scientific Reports 4, 2014, Article No. 5034.

[5] Arora S, Barak B. Computational Complexity:A Modern Approach. Cambridge:Cambridge University Press, 2009.

[6] Constantine G. Colorful isomorphic spanning trees in complete graphs. Annals of Combinatorics, 2005, 9(2):163-167.

[7] Hammadi A, Mhamdi L. A survey on architectures and energy efficiency in Data Center Networks. Computer Communications, 2014, 40(1):1-21.

[8] Stensgaard M B, Sparso J. ReNoC:A network-on-chip architecture with reconfigurable topology. In Proc. the 2nd NoCS, Apr. 2008, pp.55-64.

[9] Murali S, De Micheli G. Bandwidth-constrained mapping of cores onto NoC architectures. In Proc. DATE, Feb. 2004, pp.896-901.

[10] Gao Y, Jin Y, Chang Z, Hu W. Ultra-low latency reconfigurable photonic network on chip architecture based on application pattern. In Proc. OFC, Mar. 2009.
No related articles found!
Full text



[1] Zhu Mingyuan;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] Jin Zhiquan; Liu Chengfei; Sun Zhongxiu; Zhou Xiaofang; Chen Peipei; Gu Jianming;. Design and Implementation of a Heterogeneous Distributed Database System[J]. , 1990, 5(4): 363 -373 .
[3] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[4] Song Maoqiang; Felix Grimm; Horst Bunke;. A Prototype Expert System for Automatic Generation of Image Processing Programs[J]. , 1991, 6(3): 296 -300 .
[5] Shen Yidong;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[6] Xiang Dong; Wei Daozheng;. GLOBAL: A Design for Random Testability Algorithm[J]. , 1994, 9(2): 182 -192 .
[7] Zeng Jianchao; Hidehiko Sanada; Yoshikazu; Tezuka Xu Guangyou;. A Form-Correcting System of Chinese Characters Using a Model of Correcting Procedures of Calligraphists[J]. , 1995, 10(1): 23 -34 .
[8] Wu Xunwei; Hang Guoqiang;. Design Technique of I~2L Circuits Based on Multi-Valued Logic[J]. , 1996, 11(2): 181 -187 .
[9] Chen Fang; Yuan Baozong;. An Approach to Intelligent Speech Production System[J]. , 1997, 12(2): 185 -188 .
[10] ZHUANG Yueting; RUI Yong; Thomas S.Huang;. Video Key Frame Extraction by Unsupervised Clustering and Feedback Adjustment[J]. , 1999, 14(3): 283 -287 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved