Full metadata record
DC FieldValueLanguage
dc.contributor.authorHwang, FKen_US
dc.contributor.authorYao, YCen_US
dc.date.accessioned2019-04-02T05:58:41Z-
dc.date.available2019-04-02T05:58:41Z-
dc.date.issued1998-01-01en_US
dc.identifier.issn1432-4350en_US
dc.identifier.urihttp://dx.doi.org/10.1007/s002240000077en_US
dc.identifier.urihttp://hdl.handle.net/11536/149710-
dc.description.abstractKaklamanis, Krizanc, and Tsantilas (1991) gave an asymptotically optimal oblivious algorithm for many-one routing in hypercubes. It is shown that their argument needs to be modified in order for the algorithm to attain the asymptotic lower bound. They also applied the algorithm to permutation routing via the many-one and one-many routing phases. They claimed to save a factor of two by proposing to divide the packets into halves, routing the first half forward and the second half backward in the bit sequence. It is shown that this idea cannot reduce the total number of steps by a factor of two.en_US
dc.language.isoen_USen_US
dc.titleComments on the oblivious routing algorithm of Kaklamanis, Krizanc, and Tsantilas in the hypercubeen_US
dc.typeArticleen_US
dc.identifier.doi10.1007/s002240000077en_US
dc.identifier.journalTHEORY OF COMPUTING SYSTEMSen_US
dc.citation.volume31en_US
dc.citation.spage63en_US
dc.citation.epage66en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:A1998YH39000005en_US
dc.citation.woscount1en_US
Appears in Collections:Articles