Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort 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/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Keiichi Kaneko Articles by Yasuto Suzuki

10th Pacific Rim International Symposium on Dependable Computing (PRDC'04)

Papeete, Tahiti, French Polynesia

March 03-March 05

ISBN: 0-7695-2076-6

	ASCII Text	x
	Keiichi Kaneko, Yasuto Suzuki, "Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs," Pacific Rim International Symposium on Dependable Computing, IEEE, pp. 173-182, 10th Pacific Rim International Symposium on Dependable Computing (PRDC'04), 2004.

	BibTex	x
	@article{ 10.1109/PRDC.2004.1276568, author = {Keiichi Kaneko and Yasuto Suzuki}, title = {Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs}, journal ={Pacific Rim International Symposium on Dependable Computing, IEEE}, volume = {0}, year = {2004}, isbn = {0-7695-2076-6}, pages = {173-182}, doi = {http://doi.ieeecomputersociety.org/10.1109/PRDC.2004.1276568}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Pacific Rim International Symposium on Dependable Computing, IEEE TI - Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs SN - 0-7695-2076-6 SP173 EP182 A1 - Keiichi Kaneko, A1 - Yasuto Suzuki, PY - 2004 KW - null VL - 0 JA - Pacific Rim International Symposium on Dependable Computing, IEEE ER -

Keiichi Kaneko, Tokyo University of Agriculture and Technology

Yasuto Suzuki, Tokyo University of Agriculture and Technology

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PRDC.2004.1276568

A bubble-sort graph is a variant of Cayley graphs and it is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on nth bubble-sort graphs and propose an algorithm to obtain n - 1 disjoint paths between arbitrary two nodes in the complexity of polynomial order of n which is the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of path lengths after proving the correctness of the algorithm. Moreover, we report the results of computer experiment to evaluate average performance of the algorithm.

Citation:

Keiichi Kaneko, Yasuto Suzuki, "Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs," prdc, pp.173-182, 10th Pacific Rim International Symposium on Dependable Computing (PRDC'04), 2004

Peer Review Notice | Give Us Feedback

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