Disjoint Paths Routing in Pancake Graphs

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Keiichi Kaneko Articles by Shietung Peng

Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'06)

Taipei, Taiwan

December 04-December 07

ISBN: 0-7695-2736-1

	ASCII Text	x
	Keiichi Kaneko, Shietung Peng, "Disjoint Paths Routing in Pancake Graphs," Parallel and Distributed Computing Applications and Technologies, International Conference on, pp. 254-259, Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), 2006.

	BibTex	x
	@article{ 10.1109/PDCAT.2006.56, author = {Keiichi Kaneko and Shietung Peng}, title = {Disjoint Paths Routing in Pancake Graphs}, journal ={Parallel and Distributed Computing Applications and Technologies, International Conference on}, volume = {0}, year = {2006}, isbn = {0-7695-2736-1}, pages = {254-259}, doi = {http://doi.ieeecomputersociety.org/10.1109/PDCAT.2006.56}, 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 - Disjoint Paths Routing in Pancake Graphs SN - 0-7695-2736-1 SP254 EP259 A1 - Keiichi Kaneko, A1 - Shietung Peng, PY - 2006 KW - null VL - 0 JA - Parallel and Distributed Computing Applications and Technologies, International Conference on ER -

Keiichi Kaneko, Tokyo University of Agriculture and Technology, Japan

Shietung Peng, Hosei University, Japan

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PDCAT.2006.56

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.

Citation:

Keiichi Kaneko, Shietung Peng, "Disjoint Paths Routing in Pancake Graphs," pdcat, pp.254-259, Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), 2006

Peer Review Notice | Give Us Feedback

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