Edge-Disjoint Routing in the Undirected Hypercube
スポンサーリンク
概要
- 論文の詳細を見る
Consider a hypercube regarded as an undirected graph, with one edge between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into 8 partial permutations so that each of them can be routed by edge-disjoint paths. This improves the previous result of 16. A routing request on a hypercube is called a pairing if each node of the hypercube appears in the routing request exactly once as source or destination exclusively. We prove that any pairing on the hypercube can be partitioned into 5 subsets such that each of them can be routed by edge-disjoint paths.
- 社団法人電子情報通信学会の論文
- 1996-06-14
著者
-
Gu Qian-ping
The University Of Aizu
-
Gu Qian-ping
The University Of Aizu Aizu-wakamatsu
-
Tamaki Hisao
Tokyo Research Laboratory Ibm Japan
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
- 頂点彩色問題に対する列生成法アプローチの高速化
- テストパターンの静的圧縮における厳密解と貧欲解の比較(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平面ユークリッドTSPの分割統治法ヒューリスティツクス
- 平面グラフの分枝幅決定アルゴリズムの効率的実装
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- 合成数のAKS witnessに関する実験的研究
- 小さな碁盤における囲碁の厳密解アルゴリズム
- TD-1-12 アルゴリズムデモ発見的動的計画法 : 巡回セールスマン問題を例として
- ハイパーキューブ上の順列の同形を反復しない網羅的生成
- 教育を目的としたC言語ソース管理APIの作成とその応用(e-learning/一般)
- JavaのeラーニングのためのEclipseプラグインの開発(e-learning/一般)
- Voronoi Diagrams with Respect to Criteria on Vision Information
- 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発(セッション(1) : ゲーム情報学(1))
- Cluster Fault Tolerant Routing in Star Graphs
- Graph Orientation Problems for Multiple st-Reachability
- k-cyclic Orientations of Graphs
- グラフの自動描画における交差を考慮した巨大近傍探索
- Special Section on Discrete Mathematics and Its Applications
- Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
- Edge-Disjoint Routing in the Undirected Hypercube
- Computing directed pathwidth in O(1.89n) time
- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization