Pairwise Disjoint Paths in Pancake Graphs

Adelaide, Australia December 03-December 06

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.85

Eighth International Conference on Pa ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Naoki Sawada Articles by Keiichi Kaneko Articles by Shietung Peng

	ASCII Text	x
	Naoki Sawada, Keiichi Kaneko, Shietung Peng, "Pairwise Disjoint Paths in Pancake Graphs," Parallel and Distributed Computing Applications and Technologies, International Conference on, pp. 376-382, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007.

	BibTex	x
	@article{ 10.1109/PDCAT.2007.85, author = {Naoki Sawada and Keiichi Kaneko and Shietung Peng}, title = {Pairwise Disjoint Paths in Pancake Graphs}, journal ={Parallel and Distributed Computing Applications and Technologies, International Conference on}, volume = {0}, year = {2007}, isbn = {0-7695-3049-4}, pages = {376-382}, doi = {http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.85}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel and Distributed Computing Applications and Technologies, International Conference on TI - Pairwise Disjoint Paths in Pancake Graphs SN - 0-7695-3049-4 SP376 EP382 A1 - Naoki Sawada, A1 - Keiichi Kaneko, A1 - Shietung Peng, PY - 2007 VL - 0 JA - Parallel and Distributed Computing Applications and Technologies, International Conference on ER -

Naoki Sawada

Keiichi Kaneko

Shietung Peng

Disjoint paths problems have attracted much atten- tion due to its numerous applications in fault-tolerant routing. The pairwise disjoint paths problem is one of them. In this paper, we propose an algorithm for the pairwise disjoint paths problem in an pancake graph. The algorithm can find k disjoint paths in an n-pancake graph where k n/2 . The k disjoint paths can be constructed in O(kn) time and the maximum path length is bounded by 5n/3 + 6. Keywords: interconnection networks, polynomial time algorithm, disjoint paths.

Citation:

Naoki Sawada, Keiichi Kaneko, Shietung Peng, "Pairwise Disjoint Paths in Pancake Graphs," pdcat, pp.376-382, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.