Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hwang, FK | en_US |
dc.contributor.author | Yao, YC | en_US |
dc.date.accessioned | 2019-04-02T05:58:41Z | - |
dc.date.available | 2019-04-02T05:58:41Z | - |
dc.date.issued | 1998-01-01 | en_US |
dc.identifier.issn | 1432-4350 | en_US |
dc.identifier.uri | http://dx.doi.org/10.1007/s002240000077 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/149710 | - |
dc.description.abstract | Kaklamanis, 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.iso | en_US | en_US |
dc.title | Comments on the oblivious routing algorithm of Kaklamanis, Krizanc, and Tsantilas in the hypercube | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1007/s002240000077 | en_US |
dc.identifier.journal | THEORY OF COMPUTING SYSTEMS | en_US |
dc.citation.volume | 31 | en_US |
dc.citation.spage | 63 | en_US |
dc.citation.epage | 66 | en_US |
dc.contributor.department | 應用數學系 | zh_TW |
dc.contributor.department | Department of Applied Mathematics | en_US |
dc.identifier.wosnumber | WOS:A1998YH39000005 | en_US |
dc.citation.woscount | 1 | en_US |
Appears in Collections: | Articles |