Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Tóm tắt
Từ khóa
Tài liệu tham khảo
AHO , A V , HOPCROFT , J E ., AND ULLMAN , J D . The Destgn and Analysts of Computer Algortthms Addison-Wesley, Reading , Mass. , 1976 AHO, A V, HOPCROFT, J E., AND ULLMAN, J D. The Destgn and Analysts of Computer Algortthms Addison-Wesley, Reading, Mass., 1976
BERGE , C. , AND GHO trIt~-Hou RI , A Programming , Games and Transportatwn Networks Wiley New York , 1965 . BERGE, C., AND GHOtrIt~-HouRI, A Programming, Games and Transportatwn Networks Wiley New York, 1965.
BOROD llq, A., AND HOPCROFT , J.E. Routing, merging and sorting on parallel models of computation In Prec . 14th Annual ACM Syrup. Theory of Computing ( San Francisco , May 5-7, 1982 ), ACM, Ne,~ York, 1982, pp. 338 - 344 . 10.1145/800070.802209 BORODllq, A., AND HOPCROFT, J.E. Routing, merging and sorting on parallel models of computation In Prec. 14th Annual ACM Syrup. Theory of Computing (San Francisco, May 5-7, 1982), ACM, Ne,~ York, 1982, pp. 338-344. 10.1145/800070.802209
CHAND rtAS~K ARAN , R.Minimum ratio spanning trees. Networks 7 ( 1977 ), 335 - 342 . CHANDrtAS~KARAN, R.Minimum ratio spanning trees. Networks 7 (1977), 335-342.
CHANDRASEKARAN , R. , AND DAUGHETY , A. Problems of location on trees. D~scusston Paper No 357, The Center for Mathematical Studms m Economics and Management Science , Northwesten Univ , Evanston, Ill , 1978 . CHANDRASEKARAN, R., AND DAUGHETY, A.Problems of location on trees. D~scusston Paper No 357, The Center for Mathematical Studms m Economics and Management Science, Northwesten Univ, Evanston, Ill, 1978.
CHANDRASEKARAN , R , AND DAUGHETY , A. Locauon on tree networks, p-center and n-dtspemot problems Math. Oper. Res 6 ( 1981 ), 50 -- 57 CHANDRASEKARAN, R, AND DAUGHETY, A. Locauon on tree networks, p-center and n-dtspemot problems Math. Oper. Res 6 (1981), 50--57
CHERITON , D. , AND TARJAN , R.E. Finding minimum spanning trees. SIAM J Comput 5 ( 1976 ) 724 - 742 CHERITON, D., AND TARJAN, R.E.Finding minimum spanning trees. SIAM J Comput 5 (1976) 724-742
COFFMAN , E G . , JR Computer and Job-Shop Scheduhng . Wtley, New York , 1976 . COFFMAN, E G., JR Computer and Job-Shop Scheduhng. Wtley, New York, 1976.
DANTZIG , O B ., BLATTNER , W. , AND RAO , M R .Finding a cycle in a graph wah mmmaum cost t( time ratto with apphcation to a ship routing problem. In Theory of Graphs , P Rosentlehl (Ed) GordoJ and Breach , New York , 1967 , pp 77 - 84 DANTZIG, O B., BLATTNER, W., AND RAO, M R.Finding a cycle in a graph wah mmmaum cost t( time ratto with apphcation to a ship routing problem. In Theory of Graphs, P Rosentlehl (Ed) GordoJ and Breach, New York, 1967, pp 77-84
DINIC , E A Algorithm for soluuon of a problem of maxtmal flow tn a network wtth powe estimahon. Soy Math. Dokl 11 ( 1970 ), 1277 - 1280 . DINIC, E A Algorithm for soluuon of a problem of maxtmal flow tn a network wtth powe estimahon. Soy Math. Dokl 11 (1970), 1277-1280.
FREDERICKSON , G.N , AND JOHNSON , D B . Opttmal algorithms for generating quantlte mformatlol m X + Y and matrices wtth sorted columns . In Proc 13th Conf lnformatwn Saence and Systems, Th, lohns Hopkins Unwemty , 1979 , pp 47 - 52 . FREDERICKSON, G.N, AND JOHNSON, D B.Opttmal algorithms for generating quantlte mformatlol m X + Y and matrices wtth sorted columns. In Proc 13th Conf lnformatwn Saence and Systems, Th, lohns Hopkins Unwemty, 1979, pp 47-52.
FREDERICKSON , G,N , AND JOHNSON , D B Generating and searchng sets reduced by networks I~ Proc 7th lnt. Colloq. on Automata, Languages and Programmtng , Lecture Notes m Computer Sclencq 85 , Sprmger-Verlag , Berlin , 198l, pp. 221 - 233 FREDERICKSON, G,N, AND JOHNSON, D B Generating and searchng sets reduced by networks I~ Proc 7th lnt. Colloq. on Automata, Languages and Programmtng, Lecture Notes m Computer Sclencq 85, Sprmger-Verlag, Berlin, 198l, pp. 221-233
ICHIMORI , T , {smI, H., AND NISHIDA , T Weighted mmtmax real-valued flows J Oper Res. Sot dpn 24 ( 1981 ), 52 - 59 . ICHIMORI, T, {smI, H., AND NISHIDA, T Weighted mmtmax real-valued flows J Oper Res. Sot dpn 24 (1981), 52-59.
KAR l', R M A characterization of the mmtmum cycle mean m a digraph Discrete Math. 23 ( 1978 1 309 - 311 . KARl', R M A characterization of the mmtmum cycle mean m a digraph Discrete Math. 23 (19781 309-311.
KARZANOV , A V Determining the maxtmal flow m a network by the method of preflows Soy. Mag Dokl. 15 ( 1974 ), 434 - 437 KARZANOV, A V Determining the maxtmal flow m a network by the method of preflows Soy. Mag Dokl. 15 (1974), 434-437
LAWLER E.L.Combtnatonal Opumtzatton" Networks and Matroids. Holt Rinehart & Winston Ne~ York 1976 LAWLER E.L.Combtnatonal Opumtzatton" Networks and Matroids. Holt Rinehart & Winston Ne~ York 1976
AWLEg E.L Private o01nmun.tcdttlon AWLEg E.L Private o01nmun.tcdttlon
MALHORA , V M , PRAMODHKLIMAR , M , AND MAI-IESHWARI , S.N. An 0(1 VI' ) algorithm for fmdm maxtmum flows m networks. Computer Science Program , Indian lnst of Technology, Kanpur 20801 India , 1978 . MALHORA, V M, PRAMODHKLIMAR, M, AND MAI-IESHWARI, S.N. An 0(1VI') algorithm for fmdm maxtmum flows m networks. Computer Science Program, Indian lnst of Technology, Kanpur 20801 India, 1978.
MEGIDDO , N. Combinatorial optimization with rational objectwe functtons Math. Oper. Res ( 1979 ), 414--424. MEGIDDO, N. Combinatorial optimization with rational objectwe functtons Math. Oper. Res (1979), 414--424.
MEGIDD 0, N An apphcatwn of parallel computauon to sequential computauon The problem cost-effecttve resource allocation TWISK 202, CSIR-NRIMS , Pretona, South Africa , Mar 1981 MEGIDD0, N An apphcatwn of parallel computauon to sequential computauon The problem cost-effecttve resource allocation TWISK 202, CSIR-NRIMS, Pretona, South Africa, Mar 1981
MEGIDDO , N Applying parallel computation algorithms m the destgn of senal algonthms In Pro( 22nd IEEE Syrup . Foundauons of Computer Science, IEEE , New York , 1981 , pp 399 - 408 . MEGIDDO, N Applying parallel computation algorithms m the destgn of senal algonthms In Pro( 22nd IEEE Syrup. Foundauons of Computer Science, IEEE, New York, 1981, pp 399-408.
MEGIDDO , NThe weighted Euclidean l-center problem. Math. Oper Res 8 , 4 (Now 1983 ), t, appear. MEGIDDO, NThe weighted Euclidean l-center problem. Math. Oper Res 8, 4 (Now 1983), t, appear.
MEGIDDO , N Towards a genuinely polynomtal algonthm for linear programming SIAM J Compu , 12 , 2 ( May 1983 ), 347-353 MEGIDDO, N Towards a genuinely polynomtal algonthm for linear programming SIAM J Compu, 12, 2 (May 1983), 347-353
MEGIDDO , N. , AND TAMIR , A Finding least-distances lines. Sl AM ~ Algebraic Dtscrete Methods 2 ( June 1983 ), 207 - 221 l. MEGIDDO, N., AND TAMIR, A Finding least-distances lines. SlAM ~ Algebraic Dtscrete Methods 2 (June 1983), 207-21 l.
ME (31 DDO , N., AND TA ta R, A New results on the complexity ofp-center problems SIAM J. Compu 12 , 4 (Nov. I983), to appear. ME(31DDO, N., AND TAtaR, A New results on the complexity ofp-center problems SIAM J. Compu 12, 4 (Nov. I983), to appear.
MEGIDDO , N. , TAMIR , A , ZEMEL , E , AND CHANDRASEKARAN , R An O(nlog2n) algorithm for th K-th nearest parr m a tree with apphcations to location problems SI AM ~ Comput. 10 ( 1981 1 328 - 337 . MEGIDDO, N., TAMIR, A, ZEMEL, E, AND CHANDRASEKARAN, R An O(nlog2n) algorithm for th K-th nearest parr m a tree with apphcations to location problems SIAM ~ Comput. 10 (19811 328-337.
D, E' m, ATA , F.P. New paraBd-sorting schemes. 1 EEE Trans Comput. C-27 ( 1978 ), 669 - 673 . D,E'm, ATA, F.P. New paraBd-sorting schemes. 1EEE Trans Comput. C-27 (1978), 669-673.
SHILOACH , Y. , AND VISHKIN , U. Finding the maximum, merguag and sorting in a parallel ~omputatton model J. Algortthms 2 ( 1981 ), 88 - 102 . SHILOACH, Y., AND VISHKIN, U. Finding the maximum, merguag and sorting in a parallel ~omputatton model J. Algortthms 2 (1981), 88-102.
SHILOACH , Y , AND VISHKIN , U An O(logn) parallel connectwlty algorithm. J. Algorithms 3 ( 1982 ), 57 - 67 SHILOACH, Y, AND VISHKIN, U An O(logn) parallel connectwlty algorithm. J. Algorithms 3 (1982), 57-67
VALIANT , L.G. Parallehsm in comparison problems SIAM J. Comput 4 ( 1975 ), 348 - 355 . VALIANT, L.G.Parallehsm in comparison problems SIAM J. Comput 4 (1975), 348-355.
YAO , A.C. An O(t E Ilog log l VI ) algontlun for finding mmnunurn spannmg trees Inf. Process. Left. 4 ( 1975 ), 21 - 23 YAO, A.C. An O(t E Ilog log l VI) algontlun for finding mmnunurn spannmg trees Inf. Process. Left. 4 (1975), 21-23