Slowing down sorting networks to obtain faster sorting algorithms
Tóm tắt
Từ khóa
Tài liệu tham khảo
AHO , A. , HOPCROF r, J., AND ULLMAN , J. The Design and Analysis of Computer Algorithms . Addison-Wesley , Reading, Mass ., 1974 . AHO, A., HOPCROFr, J., AND ULLMAN, J. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.
COLE , R. , AND YAP , C . A parallel median algorithm . Inf. Process. Lett. 20 ( 1985 ), 137 - 139 . COLE, R., AND YAP, C. A parallel median algorithm. Inf. Process. Lett. 20 (1985), 137-139.
COLE , R. , SHARIR , M. , AND YAP , C. On k-hulls and related problems . SIAM J. Comput. to appear. 10.1137/0216005 COLE, R., SHARIR, M., AND YAP, C. On k-hulls and related problems. SIAM J. Comput. to appear. 10.1137/0216005
FREDERICKSON , G. , AND JOHNSON , D. Finding k-th paths and p-centers by generating and searching good data structures. ~ Algorithms 4 ( 1983 ), 61-80. FREDERICKSON, G., AND JOHNSON, D. Finding k-th paths and p-centers by generating and searching good data structures. ~ Algorithms 4 (1983), 61-80.
GABBER , O. , AND GALIL , Z . Explicit construction of linear size superconcentrators. ~ Comput . Syst. Sci. 22 ( 1981 ), 407 - 420 . GABBER, O., AND GALIL, Z. Explicit construction of linear size superconcentrators. ~ Comput. Syst. Sci. 22 (1981), 407-420.
GABOW , H. , GALIL , Z. , AND SPENCER , T. Efficient implementation of graph algorithms using contraction . In Proceedings of the 25th Annual Symposium on the Foundations of Computer Science. IEEE , New York , 1984 , 347 - 357 . GABOW, H., GALIL, Z., AND SPENCER, T. Efficient implementation of graph algorithms using contraction. In Proceedings of the 25th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1984, 347-357.
MEGIDDO , N . Combinatorial optimization with rational objective functions . Math. Oper. Res. 4 ( 1979 ), 414 - 424 . MEGIDDO, N. Combinatorial optimization with rational objective functions. Math. Oper. Res. 4 (1979), 414-424.
MEGIDDO , N. Linear time algorithms for linear programming in R3 and related problems . SIAM ~ Comput. 12 ( 1983 ), 759-776. MEGIDDO, N. Linear time algorithms for linear programming in R3 and related problems. SIAM ~ Comput. 12 (1983), 759-776.
MEGIDDO , N. Partitioning with two lines in the plane. ~ Algorithms 6 ( 1985 ), 430-433. MEGIDDO, N. Partitioning with two lines in the plane. ~ Algorithms 6 (1985), 430-433.
MEGIDDO , N. , AND TAMIR , A . New results on the complexity of p-center problems . SIAM J. Comput. 12 , 4 ( 1983 ), 751-758. MEGIDDO, N., AND TAMIR, A. New results on the complexity of p-center problems. SIAM J. Comput. 12, 4 (1983), 751-758.
PREPARATA , F . New parallel sorting schemes . IEEE Trans. Comput. C-27 ( 1978 ), 669 - 673 . PREPARATA, F. New parallel sorting schemes. IEEE Trans. Comput. C-27 (1978), 669-673.
REISCHUK , R. A fast probabilistic sorting algorithm . In Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science. IEEE , New York , 1981 , 212 - 219 . REISCHUK, R. A fast probabilistic sorting algorithm. In Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1981, 212-219.
REISER , A . A linear selection algorithm for sets of elements with weights . Inf. Process. Lett. 7 ( 1978 ), 159 - 162 . REISER, A. A linear selection algorithm for sets of elements with weights. Inf. Process. Lett. 7 (1978), 159-162.
SHILOACH , Y. , AND VISHKIN , O . Finding the maximum, merging and sorting in a parallel computation model . J. Algorithms 2 ( 1981), 88 - 102 . SHILOACH, Y., AND VISHKIN, O. Finding the maximum, merging and sorting in a parallel computation model. J. Algorithms 2 ( 1981), 88-102.