Parallel graph algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel graph algorithms

Full text

Pdf (2.40 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 16 , Issue 3 (September 1984) table of contents

Pages: 319 - 348

Year of Publication: 1984

ISSN:0360-0300

Authors

Michael J. Quinn	Washington State Univ., Pullman, WA
Narsingh Deo	Washington State Univ., Pullman, WA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 71, Downloads (12 Months): 381, Citation Count: 14

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2514.2515 What is a DOI?

REFERENCES

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	ALTON, D. A., AND ECKSTEIN, D. M~ 1979. Parallel breadth-first search of p-sparse graphs. In Proceed~ngs of the West Coast Conference on Combinator~cs, Graph Theory and Computing (Arcata, Calif., Sept. 5-7). Humbolt State Univ. Congressus Numerant~um 26.
	3	Eshrat Arjomandi, A study of parallelism in graph theory., 1976
	4	Mikhail Jibrayil Atallah, Algorithms for vlsi networks of processors, 1983
	5	Mikhail J. Atallah , S. Rao Kosaraju, Graph problems on a mesh-connected processor array (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.345-353, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802210]
	6	BATCHER, K. E. 1968. Sorting networks and their applications. In Proceedings of the Spring Joint Computer Conference (Atlantic City, N.J., Apr. 30-May 2), vol. 32. AFIPS Press, Reston, Va., pp. 307-314.
	7	BATCHER, K. E. 1979. The STARAN computer. In Infotech State of the Art Report: Supercomputers, vol. 2, C. R. Jesshope and R. C. Hockney, Eds. Infotech, Maidenhead, England, pp. 33-49.
	8	B^TCHER, K. E. 1980. Design of massively parallel processor. IEEE Trans Comput. C-29, 836- 840.
	9	BENTLEY, J. L. 1980. A parallel algorithm for constructing minimum spanning trees. J. Algorithms I, I (Mar.), 51-59.
	10	B~NTLEY, J. L, AND KUNG, H. T. 1979. A tree machine for searching problems. In Proceedings o{ the 1979 International Con{erence on Parallel Processing. IEEE, New York, pp. 257-266.
	11	BERG, H. K., BOEBERT, W. E., FRANTA, W. R., AND MOHER, T. G. 1982. Formal Methods o{ Program Verifwation and Specification. Prentice- Hall, Englewood Cliffs, N.J., chap. 6.
	12	BILARDI, G., PRACCHI, M., AND PREPARATA, F. P. 1981. A critique and appraisal of VLSI models of computation. In VLSI Systems and Computat~ons, H. T. Kung, R. Sproull, and G. Steele, Eds. Computer Science Press, Rockville, Md., pp. 81- 88.
	13	Sally Anne Browning, The tree machine: a highly concurrent computing environment, 1980
	14	BROWNING, S. A. 1980b. Algorithms for the tree machine. In Introduction to VLSI Systems, C. Mead and L. Conway, Eds. Addison-Wesley, Reading, Mass.
	15	CHANDRA, A. K. 1976. Maximal parallelism in matrix multiplicatwn. IBM Tech. Rep. RC6193, Thomas J. Watson Research Center, Yorktown Heights, N.Y. (Sept.), 9 pp.
	16	CHANDRA, A. K., AND STOCKMEYER, L. J. 1976. Alternation. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 98-108.
	17	K. Mani Chandy , J. Misra, Distributed computation on graphs: shortest path algorithms, Communications of the ACM, v.25 n.11, p.833-837, Nov 1982 [doi>10.1145/358690.358717]
	18	Bernard Chazelle , Louis Monier, A model of computation for VLSI with related complexity results, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.318-325, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802485]
	19	I-Ngo Chen, A New Parallel Algorithm for Network Flow Problems, Proceedings of the Sagamore Computer Conference on Parallel Processing, p.306-307, August 20-23, 1974
	20	CHEN, Y. K., AND FENG, T. 1973. A parallel algorithm for maximum flow problem. In Proceedings of the 1973 Computer Conference on Parallel Processing (Sagamore, N.Y.), p. 60.
	21	CHERITON, D., AND TAP. JAN, R. E. 1976. Finding mimmum spanning trees. SIAM J. Comput. 5, 4 (Dec.), 724-742.
	22	CHIN, F. Y., LAM, J., AND CHEN, i.-N. 1981. Optimal parallel algorithms for the connected component problem. In Proceedings of the 1981 International Conference on Parallel Processing. iEEE, New York, pp. 170-175.
	23	Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
	24	COOK, S. A. 1974. An observation on time-storage trade-off. J. Comput. Syst ScL 9, 3, 308-316.
	25	CRANE, B. A. 1968. Path finding with associative memory. IEEE Trans Comput. C-17, 7 (July), 691-693.
	26	CRANE, B. A., GILMARTIN, M. J., HUTTENHOFF, J. H., RVx, P. T., AND SmVELY, R. R 1972. PEPE computer architecture. COMPCON 72 Digest, IEEE, New York, pp. 57-60.
	27	DEKEL, E., AND SAHNI, S. 1982. A parallel matching algorithm for convex bipartite graphs. In Proceedings o{ the 1982 International Conference on Parallel Processzng. IEEE, New York, pp. 178- 184.
	28	DEKEL, E, AND SAHNI, S. 1983a. Parallel scheduling algorithms. Oper Res. 31, 1 (Jan.-Feb.), 24-49.
	29	DEKEL, E., AND SAHNI, S. 1983b. Binary trees and parallel scheduling algorithms. IEEE Trans Comput. C-32, 3 (Mar.), 307-315.
	30	DEKEL, E., NASSiM!, D., AND SAHNI, S. 1981. Parallel matrix and graph algorithms. SIAM J. Comput. 10, 4 (Nov.), 657-675.
	31	DENELCOR 1981. Heterogeneous element processor prmciples of operation. Publ. No. 9000001, HEP Technical Documentation Series, Denelcor, Inc., Denver, Colo.
	32	Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
	33	DEO, N., AND YOO, Y. B. 1981. Parallel algorithms for the minimum spanning tree problem. In Proceedings o{ the 1981 International Conference on Parallel Processing IEEE, New York, pp. 188- 189.
	34	DEO, N., PANG, C. Y., AND LORD, P. E. 1980. Two parallel algorithms for shortest path problems. In Proceedings of the 1980 International Con/erence on Parallel Processing. IEEE, New York, pp. 244- 253.
	35	DIJKSTRA, E. 1959. A note on two problems in connexion with graphs. Numer. Math i, 269-271.
	36	DOBKIN, D., LIPTON, R. J., AND REiSS, S. 1979. Linear programming is log-space hard for P. Inf. Process Lett. '9, 2 (Aug.), 6-97.
	37	DYMOND, P. W., AND COOK, S. A. 1980. Hardware complexity and parallel computation (preliminary version), in Proceedings o{ the 21st Annual Symposium on Foundattons o{ Computing. IEEE, New York, pp. 360-372.
	38	ECKSTEIN, D. M. 1979a. Simultaneous memory accesses. Tech. Rep. 79-6, Dept. of Computer Science, Iowa State Univ. of Science and Technology, Ames, Iowa.
	39	ECKSTEIN, D. M. 1979b. BFS and biconnectivity. Tech. Rep. 79-11, Dept. of Computer Science, Iowa State Univ. of Science and Technology, Ames, Iowa, 55 pp.
	40	ECKSTEIN, D. M., AND ALTON, D. A. 1977a. Parallel searching of non-sparse graphs. Tech. Rep. 77- 02, Dept. of Computer Science, The Umv. of iowa, Iowa City, Iowa, 35 pp.
	41	ECKSTEiN, D. M., AND ALTON, D. A. 1977b. Parallel graph processing using depth-first search. In Proceedings o{ the Con{erence on Theoretical Computer Scasnce (Waterloo, Ontario, Aug.). Univ. of Waterloo, Waterloo, Ontario, pp. 21-29.
	42	FALK, H. 1976. Reaching for the gigaflop. IEEE Spectrum 13, 10 (Oct.), 64-70.
	43	FEIERBACH, G., AND STEVENSON, D. 1979 The IL- LIAC IV. In infotech State of the Art Report. Supercomputers, vol. 2, C. R. Jesshope and R. W. Hockney, Eds. Infotech, Maidenhead, England, pp. 77-92.
	44	FLANDERS, P. M., HUNT, D. J., REDDAWAY, S. F., AND PARKINSON, D. 1977. Efficient high speed computing w~th the distributed array processor. In High Speed Computer and Algorithm Organisation. Academic Press, London, pp. 113-128.
	45	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
	46	FLYNN, M. J. 1966. Very high-speed computing systerns. Proc iEEE 54, 12 (Dec.), 1901-1909.
	47	FOSTER, M. J., AND KUNG, H. T. 1980. Design of special-purpose VLSI chips--Example and opinions. Computer 13, 1 (Jan.), 26-40.
	48	FULLER, S. H., AND OLEiNICK, P. N. 1976. Initml measurements of parallel programs m a multimmlprocessor. In Proceedings of the 13th IEEE Computer Society lnternatmnal Conference. IEEE, New York, pp. 358-363.
	49	FUNG, L. 1977. A massively parallel processing computer. In Htgh Speed Computer and Algorithm Organ~sat~on, D. J. Kuck, D. H. Lawrie, and A. H. Sameh, Eds. Academic Press, London, England, pp. 203-204.
	50	GALIL, Z. 1976. Hierarchies of complete problems. Acta Inf. 6, 77-88.
	51	Zvi Galil , Wolfgang J. Paul, An efficient general purpose parallel computer, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.247-262, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802478]
	52	Zvi Galil , Wolfgang J. Paul, An Efficient General-Purpose Parallel Computer, Journal of the ACM (JACM), v.30 n.2, p.360-387, April 1983 [doi>10.1145/322374.322382]
	53	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	54	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	55	W. Morven Gentleman, Some Complexity Results for Matrix Computations on Parallel Processors, Journal of the ACM (JACM), v.25 n.1, p.112-115, Jan. 1978 [doi>10.1145/322047.322057]
	56	GLOVER, F. 1967. Maximum watching in a convex bipartite graph. In Naval Res Logist Q. 14, 313- 316.
	57	GOLDEN, B., BODIN, L., DOYLE, T., AND STEWART, W., JR 1980 Approximate traveling salesman algorithms. Oper. Res. 28, 3 (May-June), Part 2, 694-711.
	58	Leslie M. Goldschlager, The monotone and planar circuit value problems are log space complete for P, ACM SIGACT News, v.9 n.2, p.25-29, Summer 1977 [doi>10.1145/1008354.1008356]
	59	GOLDSCHLAGER, L. M. 1977b Synchronous parallel computation. Tech. Rep. 114, Computer Science Dept., University of Toronto, Toronto, Ontario.
	60	Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.89-94, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804336]
	61	Leslie M. Goldschlager, A universal interconnection pattern for parallel computers, Journal of the ACM (JACM), v.29 n.4, p.1073-1086, Oct. 1982 [doi>10.1145/322344.322353]
	62	GOLDSCHLAGER, L. M., SHAW, R. A., AND STAPLES, J. 1982. The maximum flow problem is log space complete for P. Theor Comput. Sci 21 (Oct.), 105-111.
	63	Irene Greif, A language for formal problem specification, Communications of the ACM, v.20 n.12, p.931-935, Dec. 1977 [doi>10.1145/359897.359904]
	64	GUISAS, L. J., KUNC, H. T, AND THOMPSON, C D. 1979. Direct VLSI implementation of combinatorial algorithms. In Proceedings of the Conference on Very Large Scale Integratton' Architecture, Design, Fabrwatlon (Pasadena, Calif., Jan.). California Institute of Technology, Pasadena, Calif., pp. 509-525.
	65	Susanne Edda Hambrusch, The complexity of graph problems on vlsi, 1982
	66	HAMBRUSCH, S. E. 1983. VLSI algorithms for the connected component problem. SIAM J. Comput. 12, 2 (May), 364-365.
	67	HARARY, F. 1969. Graph Theory. Addison-Wesley, Reading, Mass.
	68	HARRISON, T. J., AND WILSON, M. W. 1983. Specialpurpose computers. In Encyclopedia of Computer Sclence and Engineering, 2nd ed., A. Ralston, Ed. Van Nostrand-Reinhold, New York, pp. 1385- 1393.
	69	HnYNES, L. S., LAU, R. L., SIEWIOREK, D. P., AND M!ZELL, D. 1982. A survey of highly parallel computing. Computer 14, 1 (Jan.), 9-24.
	70	HIGSIE, L. C. 1972. The OMEN computers: Associative array processors. In COMPCON 72 Digest, IEEE, New York, pp. 287-290.
	71	D. S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.55-57, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803631]
	72	HIRSCHBERG, D. S. 1982. Parallel graph algorithms without memory conflicts. In Proceedings o{ the 20th AUerton Conference. University of Illinois, Urbana-Champaign, II1., pp. 257-263.
	73	D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979 [doi>10.1145/359138.359141]
	74	R. W. Hockney , C. R. Jesshope, Parallel Computers Two: Architecture, Programming and Algorithms, IOP Publishing Ltd., Bristol, UK, 1988
	75	ISARAK!, T. 1976. Theoretical comparisons of search strategqes in branch-and-bound algorithms. Int. J Comput Inf. Sci. 5, 4, 315-344.
	76	JA'JA', J., AND SIMON, J. 1982. Parallel algorithms in graph theory: Planarity testing. SIAM J. Cornput 11, 2 (May), 314-328.
	77	JOHNSON, D. S. 1983. The NP-completeness column: An ongoing guide. J. Algorithms 4, 189-203.
	78	Anita K. Jones , Peter Schwarz, Experience Using Multiprocessor Systems—A Status Report, ACM Computing Surveys (CSUR), v.12 n.2, p.121-165, June 1980 [doi>10.1145/356810.356813]
	79	JONES, N. D., AND LAASER, W. T. 1976. Complete problems for deterministic polynomial time. Theor. Comput. ScL 3, 1, 105-117.
	80	KEDEM, Z. M., AND ZORaT, A. 1981. On relations between input and communication/computation in VLSI (preliminary report). In Proceedings of the 22nd Annual Symposium on Foundations o{ Computer Science. IEEE, New York, pp. 37-44.
	81	Robert M. Keller, Formal verification of parallel programs, Communications of the ACM, v.19 n.7, p.371-384, July 1976 [doi>10.1145/360248.360251]
	82	S. Rao Kosaraju, Fast parallel processing array algorithms for some graph problems(Preliminary Version), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.231-236, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804417]
	83	Dexter Kozen, Complexity of finitely presented algebras, Proceedings of the ninth annual ACM symposium on Theory of computing, p.164-177, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803406]
	84	KRUSKAL, J. B. 1956. On the shortest subtree of a graph and the traveling-s~lesman problem. Proc Amer. Math. Soc 7 (Feb.), 48-50.
	85	KU~ERA, L. 1982. Parallel computation and conflicts m memory access. Inf Process Lett. 14, 2 (20 Apr.), 93-96.
	86	KUN(~, H. T. 1980. The structure of parallel algorithms. In Advances m Computers, vol. 19, M. Yovits, Ed Academm Press, New York, pp. 65- 112
	87	KUNG, H. T. 1982. Why systolic architectures~ Computer 15, 1 (Jan.), 37-46.
	88	KUNG, H. T., AND LEISERSON, C. E. 1980. Systolic arrays for VLSi. In Introductton to VLSI Systems, C. Mead and L. Conway, Eds. Addison- Wesley, Reading, Mass., pp. 260-292.
	89	Richard E. Ladner, The circuit value problem is log space complete for P, ACM SIGACT News, v.7 n.1, p.18-20, January 1975 [doi>10.1145/990518.990519]
	90	LAMPORT, L. 1977. Proving the correctness of multlprocess programs. IEEE Trans Soft. Eng. SE-3, 7 (Mar.), 125-143.
	91	Leslie Lamport, A New Approach to Proving the Correctness of Multiprocess Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.84-97, July 1979 [doi>10.1145/357062.357068]
	92	LAWRIE, D. H. 1975. Access and alignment of data m an array processor. IEEE Trans Comput. C-24, 12 (Dec.), 1145-1155.
	93	LEIGHTON, F. T. 1981. New lower bound techniques for VLSI In Proceedings of the 22nd Annual Symposmm on Foundations of Computer Science IEEE, New York, pp. 1-12.
	94	LEISERSON, C. E. 1980. Area efficient graph layouts. In Proceedings of the 21st Annual Symposmm on Foundations o{ Computer Science IEEE, New York, pp. 270-281.
	95	Charles Eric Leiserson, Area-Efficient VLSI Computation, MIT Press, Cambridge, MA, 1997
	96	LEISERSON, C. E., AND SAXE, J. B. 1981. Opt, mizmg synchronous systems. In Proceedings of the 22nd Annual Symposmm on Foundations of Computer Scaence. IEEE, New York, pp. 23-36.
	97	S. Levialdi, On shrinking binary picture patterns, Communications of the ACM, v.15 n.1, p.7-10, Jan. 1972 [doi>10.1145/361237.361240]
	98	K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
	99	LINT, B., AND AGERWALA, T. 1981 Communication issues in the design and analysis of parallel algorithms IEEE Trans Softw Eng. SE-7, 2 (Mar.), 174-188.
	100	LIPTON, R J., AND VALDES, J. 1981. Census functions: An approach to VLSI upper bounds (preliminary version). In Proceedings of the 22nd Annual Symposium on Foundatmns of Computer Science. IEEE, New York, pp. 13-22.
	101	LITTLE, J. D. C., MURTY, K. G., SWEENEY, D. W., ANO KAREL, C. 1963. An algorithm for the traveling salesman problem. Oper. Res 11, 6 (Nov.- Dec.), 972-989.
	102	MASHBURN, H. H. 1979. The C.mmp/Hydra project: An architectural overview. Tech. Rep., Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa.
	103	MATETI, P., AND DEO, N. 1981. Parallel algorithms for the single source shortest path problem. Tech. Rep. CS-81-078, Computer Science Dept., Washington State Univ., Pullman, Wash., 38 pp.
	104	Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
	105	Jayadev Misra , K. M. Chandy, A Distributed Graph Algorithm: Knot Detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.678-686, Oct. 1982 [doi>10.1145/69622.357190]
	106	MOHAN, J. 1983. Experience with two parallel programs solving the traveling salesman problem. In Proceedings of the 1983 Internatlonal Conference on Parallel Processing IEEE, New York, pp. 191- 193
	107	MOORE, E. F. 1957. The shortest path through a maze In Proceedings of the international Symposium on the Theory of Switching, vol. 2, pp. 285-292.
	108	NASSlMI, D, AND SAHNI, S. 1979. Bltonic sort on a mesh connected parallel computer. IEEE Trans Comput. C-28, i (Jan.), 2-7.
	109	David Nassimi , Sartaj Sahni, An optimal routing algorithm for mesh-connected Parallel computers, Journal of the ACM (JACM), v.27 n.1, p.6-29, Jan. 1980 [doi>10.1145/322169.322172]
	110	NASSlMI, D., AND SAHNI, S. 1980b. Finding connected components and connected ones on a mesh-connected parallel computer. SIAM J Comput 9, 4 (Nov.), 744-757.
	111	NATH, D., AND MAHESHWARI, S. N. 1982. Parallel algorithms for the connected components and minimal spanning tree problems. Inf. Process. Lett 14, 1 (27 Mar.), 7-11.
	112	OLEINICK, P. 1978. The implementation of parallel algorithms on an asynchronous multiprocessor. Ph.D. dissertation, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa.
	113	Susan Owicki , David Gries, Verifying properties of parallel programs: an axiomatic approach, Communications of the ACM, v.19 n.5, p.279-285, May 1976 [doi>10.1145/360051.360224]
	114	Susan Owicki , Leslie Lamport, Proving Liveness Properties of Concurrent Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.455-495, July 1982 [doi>10.1145/357172.357178]
	115	PAPE, U. 1974. Implementation and efficiency of Moore-algorithms for the shortest route problem Math Program 7, 2 (Oct.), 212-222.
	116	Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
	117	PRICE, C. C. 1982. A VLSI algorithm for shortest path through a directed acyclic graph., Congressus Numerantium 34, 363-371.
	118	PRICE, C C. 1983. Task assignment using a VLSI shortest path algorithm Tech. Rep., Dept. of Computer Science, Stephen F. Austin State Umv., Nacogdoches, Tex.
	119	PRIM, R. C. 1957. Shortest connection networks and some generalizations. Bell Syst Tech J. 36, 1389- 1401.
	120	Michael Jay Quinn, The design and analysis of algorithms and data structures for the efficient solution of graph theoretic problems on mimd computers, 1983
	121	QUINN, M J., AND DEO, N. 1983. An approximate algorithm for the Euclidean traveling salesman problem Tech. Rep. CS-83-105, Computer Science Dept., Washington State Univ., Pullman, Wash
	122	REDOAWAY, S. F 1979 The DAP approach In Infotech State of the Art Report' Supercomputers, vol. 2, C. R. Jesshope and R. W. Hockney, Eds. Infotech, Maidenhead, England, pp. 311-329.
	123	REGHBATi (ARJOMANDI), E., AND CORNEIL, D. G. 1978. Parallel computations in graph theory. SIAM J. Comput 2, 2 (May), 230-237.
	124	John H. Reif, Symmetric complementation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.201-214, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802193]
	125	REtF, J. H., A~D SPmAKIS, P 1982. The expected time complexity of parallel graph and digraph algorithms. Tech. Rep. TR-11-82, A~ken Computation Laboratory, Harvard Umv, Cambridge, Mass
	126	Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
	127	ROSENKRANTZ, D., STEARNS, R, AND LEWIS, P. 1974. Approximate algorithms for the traveling saleperson problem. In Proceedings of the 15th Annual iEEE Symposium on Switching and Automata Theory. IEEE, New York, pp. 33-42.
	128	SAVAGE, C. 1977. Parallel algorithms for graph theoretic problems Ph D. dissertation, Mathematics Dept., Univ. of Illinois, Urbana, II1.
	129	SAVAGE, C. 1981. A systolic data structure chip for connectivity problems. In VLSI Systems and Computations, H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., Eds. Computer Science Press, Rockville, Md.
	130	SAVAGE, C., AND JA'JA', J. 1981. Fast, efficient parallel algorithms for some graph problems. SIAM J Comput. I0, 4 (Nov.), 682-690.
	131	SAVAGE, J. E 1981. Planar circuit complemty and the performance of VLSI algorithms. In VLSI Systems and Computations, H T. Kung, R F. Sproull, and G. Steele, Jr., Eds. Computer Science Press, Rockville, Md., pp. 61-66.
	132	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]
	133	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]
	134	SIEGEL, H. J. 1979. A model of SIMD machines and a comparison of various interconnection networks IEEE Trans. Comput. C-28, 12 (Dec.), 907-917.
	135	SMITH, B. J. 1978 A pipelined shared resource MIMD computer. In Proceedings of the 1978 International Conference on Parallel Processing. IEEE, New York, pp. 6-8.
	136	SOLLIN, M. 1977. An algorithm attributed to Sollin. In lntroductton to the Design and Analysis of Algorzthms, S. E. Goodman and S. T. Hedetniemi, Eds McGraw-Hill, New York, sect. 5.5.
	137	STONE, H S. 1971. Parallel processing with the perfect shuffle. IEEE Trans Comput. C-20, 2 (Feb.), 153-161
	138	STONE, H. S. 1980. Parallel computers. In lntroduct~on to Computer Architecture, H. S. Stone, Ed. Science Research Associates Chicago, I11., chap. 8.
	139	SWAN, R. J., BECHTOLSHEIM, A., LAI, K.-W., AND OUSTERHOUT, J. K. 1977. The implementatwn of the Cm* multi-microprocessor. In Proceedings of the National Computer Conference (Dallas, Tex., June 13-16), vol. 46. AFIPS Press, Reston, Va., pp. 645-655.
	140	C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
	141	Clark David Thompson, A complexity theory for vlsi, 1980
	142	C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Proceedings of the eighth annual ACM symposium on Theory of computing, p.58-64, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803632]
	143	Yung H. Tsin , Francis Y. Chin, Efficient parallel algorithms for a class of graph theoretic problems, SIAM Journal on Computing, v.13 n.3, p.580-599, August 1984 [doi>10.1137/0213036]
	144	Frances Lucretia Van Scoy, Parallel algorithms in cellular spaces., 1976
	145	VISHKIN, U. 1983. Implementation of simultaneous memory access in models that forbid it. J. Algonthms 4, 1 (Mar.), 45-50.
	146	VUILLEMIN, J. E. 1983. A combinatorial limit to the computing power of VLSI circuits. IEEE Trans. Comput C-32, 3 (Mar.), 294-300.
	147	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	148	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977 [doi>10.1145/356707.356711]
	149	WULF, W., AND HARBISON, S. P. 1978. Reflections in a pool of processors. Tech. Rep., Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa.
	150	James Christopher Wyllie, The complexity of parallel computations, 1979
	151	YAO, C.-C. 1975. An O(IEI log log }V}) algorithm for finding minimum spanning trees. Inf. Process. Lett. 4, 1 (Sept.), 21-23.
	152	S. S. Yau , H. S. Fung, Associative Processor Architecture—a Survey, ACM Computing Surveys (CSUR), v.9 n.1, p.3-27, March 1977 [doi>10.1145/356683.356685]
	153	Year Back Yoo, Parallel processing for some network optimization problems, 1983

CITED BY 14

	Douglas W. Jones, Concurrent simulation: an alternative to distributed simulation, Proceedings of the 18th conference on Winter simulation, p.417-423, December 08-10, 1986, Washington, D.C., United States
	Sujit Dey , Pradip K. Srimani, Parallel VLSI computation of all shortest paths in a graph, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.373-379, February 1988, Atlanta, Georgia, United States
	Douglas W. Jones, Concurrent operations on priority queues, Communications of the ACM, v.32 n.1, p.132-137, Jan. 1989
	Francis Suraweera , Prabir Bhattacharya, A parallel algorithm for the minimum spanning tree on an SIMD machine, Proceedings of the 1992 ACM annual conference on Communications, p.473-476, March 03-05, 1992, Kansas City, Missouri, United States
	Edward Omiecinski , Peter Scheuermann, A parallel algorithm for record clustering, ACM Transactions on Database Systems (TODS), v.15 n.4, p.599-624, Dec. 1990
	S. Upendra Rao , G. P. Shattacharjee , A. K. Majumdar, Parallel implementation of an efficient microcode compaction algorithm, ACM SIGMICRO Newsletter, v.17 n.3, p.13-19, Dec. 1986
	E. R. Omiecinski, A Parallel Algorithm for Relational Database Normalization, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.415-423, October 1990
	Yujie Han , Robert A. Wagner, An efficient and fast parallel-connected component algorithm, Journal of the ACM (JACM), v.37 n.3, p.626-642, July 1990
	L. M. Kirousis, Effectively Labeling Planar Projections of Polyhedra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.2, p.123-130, February 1990
	V. N. Rao , V. Kumar, Concurrent Access of Priority Queues, IEEE Transactions on Computers, v.37 n.12, p.1657-1665, December 1988
	S. Olariu , Z. Wen, Optimal Parallel Initialization Algorithms for a Class of Priority Queues, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.423-429, October 1991
	William McLendon, III , Bruce Hendrickson , Steven J. Plimpton , Lawrence Rauchwerger, Finding strongly connected components in distributed graphs, Journal of Parallel and Distributed Computing, v.65 n.8, p.901-910, August 2005
	Chang-Biau Yang , R. C. T. Lee , Wen-Tsuen Chen, Parallel Graph Algorithms Based Upon Broadcast Communications, IEEE Transactions on Computers, v.39 n.12, p.1468-1472, December 1990
	Kiran Ijaz , Umar Manzoor , Arshad Ali Shahid, Routing framework for FTIMA: a fault tolerance infrastructure for mobile agents, Proceedings of the 7th WSEAS International Conference on Artificial intelligence, knowledge engineering and data bases, p.148-153, February 20-22, 2008, Cambridge, UK

INDEX TERMS

Classification:
B. Hardware
B.7 INTEGRATED CIRCUITS
B.7.1 Types and Design Styles
Subjects: Algorithms implemented in hardware

C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**; Single-instruction-stream, multiple-data-stream processors (SIMD)

E. Data

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory

REVIEW

"Andranik Mirzaian : Reviewer"

After an introduction and terminology section, this survey article contains a brief discussion of various parallel computational models, such as SIMD, MIMD and their variants, systolic arrays, and associative processors. There is a section on un more...

Collaborative Colleagues:

Michael J. Quinn: colleagues

Narsingh Deo: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player