Disjoint paths routing in pancake graphs

被引：0
|
作者：
Kaneko, Keiichi [1 ]
Peng, Shietung [2 ]
机构：
[1] Tokyo Univ Agr & Technol, Fac Engn, Koganei, Tokyo 1848588, Japan
[2] Hosei Univ, Dept Comp Sci, Tokyo 1848584, Japan
来源：
SEVENTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PROCEEDINGS | 2006年
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper we propose efficient algorithms that find disjoint paths for node-to-node and node-to-set routing in pancake graphs. For an n-pancake graph, the algorithms can find n-1 disjoint paths of small maximum length with optimal time complexity. That is, the n-1 paths can be constructed in O(n(2)) time and the maximum length is bounded by 5n/3 + 6.
引用
收藏
页码：254 / +
页数：3
相关论文
共 50 条
12345