Applying Parallel Computation Algorithms in the Design of Serial Algorithms

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Ronald I. Becker , Stephen R. Schach , Yehoshua Perl, A Shifting Algorithm for Min-Max Tree Partitioning, Journal of the ACM (JACM), v.29 n.1, p.58-67, Jan. 1982 [doi>10.1145/322290.322294]
	3	BERGE, C., AND GHOtrIt~-HouRI, A Programming, Games and Transportatwn Networks Wiley New York, 1965.
	4	A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
	5	CHANDrtAS~KARAN, R.Minimum ratio spanning trees. Networks 7 (1977), 335-342.
	6	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.
	7	CHANDRASEKARAN, R, AND DAUGHETY, A. Locauon on tree networks, p-center and n-dtspemot problems Math. Oper. Res 6 (1981), 50--57
	8	CHERITON, D., AND TARJAN, R.E.Finding minimum spanning trees. SIAM J Comput 5 (1976) 724-742
	9	COFFMAN, E G., JR Computer and Job-Shop Scheduhng. Wtley, New York, 1976.
	10	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
	11	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.
	12	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.
	13	Greg N. Frederickson , Donald B. Johnson, Generating and Searching Sets Induced by Networks, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.221-233, July 14-18, 1980
	14	Zvi Galil , Nimrod Megiddo, A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort, Journal of the ACM (JACM), v.26 n.1, p.58-64, Jan. 1979 [doi>10.1145/322108.322114]
	15	Daniel Mier Gusfield, Sensitivity analysis for combinatorial optimization, 1980
	16	Dan Gusfield, Parametric Combinatorial Computing and a Problem of Program Module Distribution, Journal of the ACM (JACM), v.30 n.3, p.551-563, July 1983 [doi>10.1145/2402.322391]
	17	ICHIMORI, T, {smI, H., AND NISHIDA, T Weighted mmtmax real-valued flows J Oper Res. Sot dpn 24 (1981), 52-59.
	18	KARl', R M A characterization of the mmtmum cycle mean m a digraph Discrete Math. 23 (19781 309-311.
	19	KARZANOV, A V Determining the maxtmal flow m a network by the method of preflows Soy. Mag Dokl. 15 (1974), 434-437
	20	LAWLER, E.L.Combtnatonal Opumtzatton" Networks and Matroids. Holt, Rinehart & Winston, Ne~ York, 1976
	21	AWLEg, E.L Private o01nmun.tcdttlon
	22	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.
	23	MEGIDDO, N. Combinatorial optimization with rational objectwe functtons Math. Oper. Res (1979), 414--424.
	24	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
	25	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.
	26	MEGIDDO, NThe weighted Euclidean l-center problem. Math. Oper Res 8, 4 (Now 1983), t, appear.
	27	MEGIDDO, N Towards a genuinely polynomtal algonthm for linear programming SIAM J Compu, 12, 2 (May 1983), 347-353
	28	MEGIDDO, N., AND TAMIR, A Finding least-distances lines. SlAM ~ Algebraic Dtscrete Methods 2 (June 1983), 207-21 l.
	29	ME(31DDO, N., AND TAtaR, A New results on the complexity ofp-center problems SIAM J. Compu 12, 4 (Nov. I983), to appear.
	30	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.
	31	Yehoshua Perl , Stephen R. Schach, Max-Min Tree Partitioning, Journal of the ACM (JACM), v.28 n.1, p.5-15, Jan. 1981 [doi>10.1145/322234.322236]
	32	D,E'm, ATA, F.P. New paraBd-sorting schemes. 1EEE Trans Comput. C-27 (1978), 669-673.
	33	SHILOACH, Y., AND VISHKIN, U. Finding the maximum, merguag and sorting in a parallel ~omputatton model J. Algortthms 2 (1981), 88-102.
	34	SHILOACH, Y, AND VISHKIN, U An O(logn) parallel connectwlty algorithm. J. Algorithms 3 (1982), 57-67
	35	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
	36	Daniel Dominic Kaplan Sleator, An o(nm log n) algorithm for maximum network flow, 1981
	37	VALIANT, L.G.Parallehsm in comparison problems SIAM J. Comput 4 (1975), 348-355.
	38	YAO, A.C. An O(t E Ilog log l VI) algontlun for finding mmnunurn spannmg trees Inf. Process. Left. 4 (1975), 21-23
	39	YtYVAL, G An algorithm for finding all the shortest paths using Nzs~ infinite-precision multiplications, lnf Process. Lett 4 (1976), 155-156.