Routing Functions-An Effective Technology for Constructing Node-Disjoint Paths in Hypercubes

台灣東部新協發與佳豐定置漁場漁況變動比較分析（II）~季節別漁獲組成與產量分析~

賴正男(Cheng-Nan Lai)

《高雄海洋科大學報》 26期 (2012/03) Pp. 81-95

https://doi.org/10.6983/KHHYKTHP.201203.0082

摘要

繞徑函數已被證明在類超立方體網路上建構節點互斥路徑是有效率的。在最小繞徑函數的幫助下，n條分別從一個來源節點至其他（不需完全不同的）n個目標節點的節點互斥路徑，已在n維超立方體上建構出，使得在最差情況下其最大長度為最短。在本篇論文中，我們要證明，在最大繞徑函數的幫助下，m條分別從一個來源節點至其他（不需完全不同的）m個目標節點的節點互斥路徑，可在n維超立方體上建構出，使得其長度總和為最小，其中m≤n。建構這些m條路徑需要的最差時間複雜度是O(m^3n^1.5)，這比之前的O(m^2n^2.5+mn^3)結果是較為有效率的。開發各式各樣的繞徑函數並研究其特性是一個令人有趣的研究主題。

關鍵字

超立方體 ； 節點互斥路徑 ； 配對 ； 最佳化問題

並列摘要

Routing functions have been shown effective in constructing node-disjoint paths in hypercube-like networks. By the aid of minimal routing functions, n node-disjoint paths from a source node to other n (not necessarily distinct) destination nodes, respectively, have been constructed in an n-dimensional hypercube so that their maximal length is minimized in the worst case. In this paper, we show that by the aid of maximal routing functions, m node-disjoint paths from a source node to other m (not necessarily distinct) destination nodes, respectively, can be constructed in an n-dimensional hypercube so that their total length is minimized, where m≤n. The construction of these m disjoint paths has worst- case time complexity O(m^3n^1.5), which is more efficient than the previous result of O(m^2n^2.5+mn^3). It is an interesting research topic to exploit various routing functions and study their properties.

並列關鍵字

Hypercube ； node-disjoint paths ； matching ； optimization problem