Routing a Permutation in the Hypercube by Two Sets of Edge - Disjoint Paths

• Item type: SIG Technical Reports(1)
• 公開日: 1995-11-17
• タイトル: Routing a Permutation in the Hypercube by Two Sets of Edge - Disjoint Paths
• タイトル / 言語: en
• タイトル: Routing a Permutation in the Hypercube by Two Sets of Edge - Disjoint Paths
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: The Department of Computer Software University of Aizu
• 著者所属: Tokyo Research Laboratory IBM Japan
• 著者所属(英): en
• 著者所属(英): The Department of Computer Software, University of Aizu
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan
• 著者名: Qian-PingGu; Hisao, Tamaki
• 著者名(英): Qian-Ping, Gu; Hisao, Tamaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Consider a hypercube regarded as a directed graph with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths. This result implies that the hypercube can be made rearrangeable by virtually duplicating each edge through time-sharing (or through the use of two wavelengths in the case of optical connection) rather than by physically adding edges as in previous approaches. When our goal is to route as many source-destination pairs of the given permutation as possible by edge-disjoint paths our result gives a 2-approximate solution which improves previous ones.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider a hypercube regarded as a directed graph, with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths. This result implies that the hypercube can be made rearrangeable by virtually duplicating each edge through time-sharing (or through the use of two wavelengths in the case of optical connection), rather than by physically adding edges as in previous approaches. When our goal is to route as many source-destination pairs of the given permutation as possible by edge-disjoint paths, our result gives a 2-approximate solution which improves previous ones.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 109(1995-AL-048), p. 47-53, 発行日 1995-11-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会