Abstract
Modern day civilization highly relies on all kinds of interconnection networks, such as VLSI (Very Large Scale Integrated Circuit) wire connections, power line networks, communication networks, internet connections, etc., and the scale of these networks are growing exponentially. Unfortunately there is no practically feasible optimal and near-optimal algorithm for large scale reliable network generation and hence most are either over or under designed. Therefore, we propose in the paper an efficient near-optimal k-connected robust interconnection network (k-RN) generation algorithm, CORONA, which can produce highly reliable networks which can tolerate k - 1 connection open faults. The proposed algorithm is of efficient O(n log n)-time complexity and can minimize total connection length. As real-world networks often evolve through actual use, we also design an incremental CORONA for cases of vertex insertion or deletion to an existing k-RN. Experimental results show that CORONA can effectively handle large networks with 100k vertices in merely a few minutes each. The quality in terms of total connection length of CORONA is verified to be within 1.6% to a well-known O(n3) 1.5-approximation algorithm, and within 4.7% to an exact optimum solution on average.