Article

Free access

Graph problems on a mesh-connected processor array (Preliminary Version)

Authors:

Mikhail J. Atallah,

S. Rao KosarajuAuthors Info & Claims

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

Pages 345 - 353

https://doi.org/10.1145/800070.802210

Published: 05 May 1982 Publication History

Abstract

We give O(n) step algorithms for solving a number of graph problems on an n×n array of processors. The problems considered include: marking the bridges of an undirected graph, marking the articulation points of such a graph, finding the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems.

References

[1]

Aho, A., Hopcroft, J. E. and Ullman, J. D., The Design and Analysis of Computer Agorithms, Addison-Wesley, Reading, MA, 1974.

Digital Library

[2]

Atallah, M. J., "Finding the Cyclic Index of an Irreducible, Nonnegative Matrix," TR. 81-6, Dept. of Elec. Engr. and Comp. Sci., Johns Hopkins University.

[3]

Berge, C., The Theory of Graphs and Its Applications, Wiley, NY, 1958.

[4]

Cannon, L. E., "A Cellular Computer to Implement the Kalman Filter Algorithm," Ph.D. thesis, Montana State University, 1969.

Digital Library

[5]

Christopher, T. W., "An Implementation of Warshall's Algorithm for Transitive Closure on a Cellular Computer," Rep. No. 36, Inst. of Comp. Res., Univ. of Chicago, February 1973.

[6]

Flynn, M. J. and Kosaraju, S. R., "Processes and Their Interactions," Kybernetics, Thales Publication, 1976, pp. 159-163.

[7]

Guibas, L. J., Kung, H. T. and Thompson, C. D., "Direct VLSI Implementation of Combinatorial Algorithms," Proceedings 1979 Caltech Conf. on VLSI, pp. 509-525.

[8]

Harary, F., Graph Theory, Addison-Wesley, Reading, MA, 1969.

[9]

Itai, A. and Rodeh, M., "Finding a Minimum Circuit in a Graph," SIAM J. on Computing, 1978, Vol. 7, No. 4, pp. 413-423.

Digital Library

[10]

Knuth, D. E. Lecture notes delivered at the Matematisk Institutt of the Univ. of Oslo, Norway, 1972-73.

[11]

Kosaraju, S. R., "Recognition of Context-Free and Stack Languages," IEEE Conf. Record of 10th Annual Symp. on Switching and Automata Theory, 129-132, 1969.

[12]

Kosaraju, S. R., "Speed of Recognition of Context-Free Languages by Array Automata," SIAM J. on Computing, 1975, No. 4, pp. 331-340.

Digital Library

[13]

Levitt, K. N. and Kautz, W. H., "Cellular Arrays for the Solution of Graph Problems," CACM, V. 15, No. 9, Sep. 1972, pp. 789-801.

Digital Library

[14]

Mead, C. A. and Conway, L. A., Introduction to VLSI Systems, Addison-Wesley, 1979.

Digital Library

[15]

Nassimi, D. and Sahni, S. K., "Bitonic Sort on a Mesh-Connected Parallel Computer," IEEE Trans. on Computers, Vol. C-28, No. 1, pp. 2-7, 1979.

[16]

Nassimi, D. and Sahni, S. K., "Data Broadcasting in SIMD Computers," IEEE Trans. on Computers, 101-106, 1981.

[17]

Savage, C., "A Systolic Data Structure Chip for Connectivity Problems," CMU Conference on VLSI Systems and Computations, 296-300, 1981.

[18]

Thompson, C. D. and Kung, H. T., "Sorting on a Mesh-Connected Parallel Computer," CACM, Vol. 20, No. 4, pp. 263-271, April 1977.

Digital Library

[19]

Van Scoy, F. C., "The Parallel Recognition of Classes of Graphs," IEEE Trans. on Computers, Vol. C-29, No. 7, p. 563, July 1980.

[20]

Warshall, S., "A Theorem on Boolean Matrices," JACM, Vol. 9, pp. 11-12, 1962.

Digital Library

Cited By

Chlebus BGasieniec L(2005)Optimal pattern matching on meshesSTACS 9410.1007/3-540-57785-8_143(213-224)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57785-8_143
Aggarwal ACarter JKosaraju S(2005)Optimal tradeoffs for addition on systolic arraysVLSI Algorithms and Architectures10.1007/3-540-16766-8_6(57-69)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-16766-8_6
Aggarwal ACarter JKosaraju S(1991)Optimal tradeoffs for addition on systolic arraysAlgorithmica10.1007/BF017590346:1-6(49-71)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1007/BF01759034
Show More Cited By

Graph problems on a mesh-connected processor array (Preliminary Version)
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G@?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-...
Removable edges in a k-connected graph and a construction method for k-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G@?e is still k-connected, where G@?e denotes the graph obtained from G by deleting e to get G-e and, for any end vertex of e with degree k-1 in G-e, say x, deleting x and then adding ...
Collapsible subgraphs of a 4-edge-connected graph
Abstract
Jaeger in 1979 showed that every 4-edge-connected graph is supereulerian, graphs that have spanning eulerian subgraphs. Catlin in 1988 sharpened Jaeger’s result by showing that every 4-edge-connected graph is collapsible, graphs that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

May 1982

408 pages

ISBN:0897910702

DOI:10.1145/800070

Copyright © 1982 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 May 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,394 of 4,375 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
69
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)9

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chlebus BGasieniec L(2005)Optimal pattern matching on meshesSTACS 9410.1007/3-540-57785-8_143(213-224)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57785-8_143
Aggarwal ACarter JKosaraju S(2005)Optimal tradeoffs for addition on systolic arraysVLSI Algorithms and Architectures10.1007/3-540-16766-8_6(57-69)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-16766-8_6
Aggarwal ACarter JKosaraju S(1991)Optimal tradeoffs for addition on systolic arraysAlgorithmica10.1007/BF017590346:1-6(49-71)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1007/BF01759034
Meyer auf der Heide F(1989)Computing minimum spanning forests on 1- and 2-dimensional processor arraysSTACS 8910.1007/BFb0028983(181-192)Online publication date: 1989
https://doi.org/10.1007/BFb0028983
Meyer auf der Heide FWanka R(1989)Time-optimal simulations of networks by universal parallel computersSTACS 8910.1007/BFb0028978(120-131)Online publication date: 1989
https://doi.org/10.1007/BFb0028978
Di Gesu VMachi A(1988)Two Parallel Algorithms for the Analysis of Random ImagesReal-Time Object Measurement and Classification10.1007/978-3-642-83325-0_7(111-117)Online publication date: 1988
https://doi.org/10.1007/978-3-642-83325-0_7
Li LMarsland TDavis PMcClintock V(1987)A parallel algorithm for finding a maximum flow in 0-1 networksProceedings of the 15th annual conference on Computer Science10.1145/322917.322953(231-234)Online publication date: 1-Feb-1987
https://dl.acm.org/doi/10.1145/322917.322953
Ribeiro C(1987)Parallel Computer Models and Combinatorial AlgorithmsSurveys in Combinatorial Optimization10.1016/S0304-0208(08)73240-7(325-364)Online publication date: 1987
https://doi.org/10.1016/S0304-0208(08)73240-7
Doshi KVarman P(1987)Efficient graph algorithms using limited communication on a fixed-size array of processorsSTACS 8710.1007/BFb0039596(76-87)Online publication date: 1987
https://doi.org/10.1007/BFb0039596
Chung MToy EGupta AWinkler SStone H(1986)A parallel computer based on cube connected cycles for wafer scale integrationProceedings of 1986 ACM Fall joint computer conference10.5555/324493.324583(325-335)Online publication date: 2-Nov-1986
https://dl.acm.org/doi/10.5555/324493.324583
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents