完整後設資料紀錄
DC 欄位語言
dc.contributor.authorHwang, FKen_US
dc.contributor.authorYao, YCen_US
dc.contributor.authorDasgupta, Ben_US
dc.date.accessioned2014-12-08T15:42:52Z-
dc.date.available2014-12-08T15:42:52Z-
dc.date.issued2002-01-06en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://dx.doi.org/10.1016/S0304-3975(00)00279-6en_US
dc.identifier.urihttp://hdl.handle.net/11536/29071-
dc.description.abstractOblivious permutation routing in binary d-cubes has been well studied in the literature. In a permutation routing, each node initially contains a packet with a destination such that all the 2(d) destinations are distinct. Kaklamanis et al. (Math. Syst. Theory 24 (1991) 223-232) used the decomposability of hypercubes into Hamiltonian circuits to give an asymptotically optimal routing algorithm. The notion of "destination graph" was first introduced by Borodin and Hopcroft to derive lower bounds on routing algorithms. This idea was recently used by Grammatikakis et al. (Proceedings of the Advancement in Parallel Computing, Elsevier, Amsterdam, 1993) to construct many-one routing algorithms for the binary 2-cube and 3-cube. In the present paper, further theoretical development is made along this line. It is then applied to obtain algorithms for binary d-cubes with d up to 12, which compare favorably with the above-mentioned "Hamiltonian circuit" algorithm. Some results on t-nary cubes with t greater than or equal to 3 are also obtained. (C) 2002 Published by Elsevier Science B.V.en_US
dc.language.isoen_USen_US
dc.subjectpermutation routingen_US
dc.subjecthypercubeen_US
dc.subjectoblivious routingen_US
dc.subjectdestination graphen_US
dc.subjectt-nary cubeen_US
dc.titleSome permutation routing algorithms for low-dimensional hypercubesen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/S0304-3975(00)00279-6en_US
dc.identifier.journalTHEORETICAL COMPUTER SCIENCEen_US
dc.citation.volume270en_US
dc.citation.issue1-2en_US
dc.citation.spage111en_US
dc.citation.epage124en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:000173012000003-
dc.citation.woscount7-
顯示於類別:期刊論文


文件中的檔案:

  1. 000173012000003.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。