Browsing by Author "Yao, YC"

Now showing 1 - 4 of 4

Comments on the oblivious routing algorithm of Kaklamanis, Krizanc, and Tsantilas in the hypercube
(1998-01-01)
Hwang, FK
;
Yao, YC
;
應用數學系
;
Department of Applied Mathematics
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.
Comments on the oblivious routing algorithm of Kaklamanis, Krizanc, and Tsantilas in the hypercube
(1998-01-01)
Hwang, FK
;
Yao, YC
;
應用數學系
;
Department of Applied Mathematics
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.
Localizing combinatorial properties for partitions on block graphs
(1999)
Chang, GJ
;
Hwang, FK
;
Yao, YC
;
應用數學系
;
Department of Applied Mathematics
We extend the study on partition properties from the set partition to the graph partition, especially for the class of connected block graphs which includes trees. We introduce seventeen partition properties and determine their inter-relations. The notions of k-consistency and k-sortability were studied in the set partition to localize the properties, i.e., a global property can be verified through checking local conditions. We carry on these studies for partitions on connected block graphs. In particular, we completely determine the consistency for an the seventeen properties.
Some permutation routing algorithms for low-dimensional hypercubes
(2002-01-06)
Hwang, FK
;
Yao, YC
;
Dasgupta, B
;
應用數學系
;
Department of Applied Mathematics
Oblivious 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.