A simple parallel algorithm for the maximal independent set problem

ABSTRACT

Simple parallel algorithms for the maximal independent set (MIS) problem are presented. The first algorithm is a Monte Carlo algorithm with a very local property. The local property of this algorithm may make it a useful protocol design tool in distributed computing environments and artificial intelligence. One of the main contributions of this paper is the development of powerful and general techniques for converting Monte Carlo algorithms into deterministic algorithms. These techniques are used to convert the Monte Carlo algorithm for the MIS problem into a simple deterministic algorithm with the same parallel running time.

REFERENCES

• ACGS: Alexi, W., Chor, B., Ooldreich, O. and Schnorr, C. RSAIRabin Bits are ~ + p'-oly(toglV) Stcure, 25tn FOCS, October 1984
• ABI: A!on, N., Babai, L., and ltai, A.,A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem, private communication
• Br: Brooks, R.L., On cotouring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-I97, 1941
• Co: Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
• CL: Cook, S. and Luby, M. A Fast Parattet Algorithm for Flndln8 a Truth Assignment to a 2-CNF Formuta, paper in preparation
• Fe: Feldman, J. A. A Connecttontst Modet of Visual Memory, Parallel Models of Associative Memory, G~. Hinton and J.A. Anderson editors, Hillsdale, N.J., Lawrence Erlbaum Associates, publishers, 1981
• Fr: Feller, W. An introduction to Probability Theory and Its Applications, vol. 1,3,d edition, 1968, John Wiley and Sons, publishers
• Ga: Galambos, J., Bonferront inequatittes, The Annals of Probability, 1977, vol. 5, no. 4, 577-581
• Go: Leslie M. Goldschlager, A computational theory of higher brain function, Stanford University, Stanford, CA, 1984
• Ho: Hopfield, J. J., Neural networks and physical system with emergent collective computational abilities, Proceedings National Academy of Sciences, vol. 79, pp. 2554-2558, April 1982
• Hi: Hinton, G.E., Sejnowski, T. and Ackley, D., Boltzmann Machines: Constraint Satisfaction Networks that Learn, technical report CMU-CS-84- 119
• II: Israeli, A. and Itai, A. A Fast and Simple Random. ized Parallel Algorithm for Maximal Matching, Computer Science Dept., Technion, Haifa Israel, 1984
• IS: Israeli, A. and Shiloach, Y. An improved Maximal Matching Parallel Algorithm, Tech. Rep. 333, Computer Science Dept., Technion, Haifa Israel, 1984
• Kf1: Karloff, H., Randomized Parallel Algorithm for the Odd-Set Cover Problem, preprint
• Kf2: Karloff, H., private communication
• KSS: Karlogf, H., Shmoys, D. and Sotoker, D., Efficient Parallel Algorithms for Graph Coloring and Partitioning Problems, preprint
• KW: Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
• KUW: Kup, R.M., Upfal, E. and Wigder~a, A., Con- #tructing a Perfect Matching is in Random NC, this conference
• Le: Lev O. Size Bounds and Parallel Algorithms for Networks, Report CST-8-80, Department of Computer Science, University of Edinburgh (1980)
• Ts: Tsotsos, J. Representational Axes and Temporal Cooperative Processes, Technical Report RBCV- 84-2, University of Toronto, April 1984
• Va: Vaiiant, L. G. Parallel Computation, Proceedings 7'a IBM Symposium on Malhematical Foundations of Computer Science (1982)

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory, Verification