More Web Proxy on the site http://driver.im/

Article

Free access

A simple parallel algorithm for the maximal independent set problem

Author:

M LubyAuthors Info & Claims

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

Pages 1 - 10

https://doi.org/10.1145/22145.22146

Published: 01 December 1985 Publication History

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

[1]

Alexi, W., Chor, B., Ooldreich, O. and Schnorr, C. RSAIRabin Bits are ~ + p'-oly(toglV) Stcure, 25tn FOCS, October 1984

[2]

A!on, N., Babai, L., and ltai, A.,A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem, private communication

[3]

Brooks, R.L., On cotouring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-I97, 1941

[4]

Cook, S. A Taxonomy of Problems with Fast Parat. let Algorithms, to appear in Information and Control

Digital Library

[5]

Cook, S. and Luby, M. A Fast Parattet Algorithm for Flndln8 a Truth Assignment to a 2-CNF Formuta, paper in preparation

[6]

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

[7]

Feller, W. An introduction to Probability Theory and Its Applications, vol. 1,3,d edition, 1968, John Wiley and Sons, publishers

[8]

Galambos, J., Bonferront inequatittes, The Annals of Probability, 1977, vol. 5, no. 4, 577-581

[9]

Goldschlager, L.M. A Computational Theory oj Higher Brain Function, Technical Report, Stanford University, April 1984

Digital Library

[10]

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

[11]

Hinton, G.E., Sejnowski, T. and Ackley, D., Boltzmann Machines: Constraint Satisfaction Networks that Learn, technical report CMU-CS-84- 119

[12]

Israeli, A. and Itai, A. A Fast and Simple Random. ized Parallel Algorithm for Maximal Matching, Computer Science Dept., Technion, Haifa Israel, 1984

[13]

Israeli, A. and Shiloach, Y. An improved Maximal Matching Parallel Algorithm, Tech. Rep. 333, Computer Science Dept., Technion, Haifa Israel, 1984

[14]

Karloff, H., Randomized Parallel Algorithm for the Odd-Set Cover Problem, preprint

[15]

Karloff, H., private communication

[16]

Karlogf, H., Shmoys, D. and Sotoker, D., Efficient Parallel Algorithms for Graph Coloring and Partitioning Problems, preprint

[17]

Karp, R.M. and Wigderson, A. A Fast Parallel Algorithm for the Maximal Independent Set Prob. tern, Proceedings 16tk ACM 5TOC (1984), pp. 266. 272

Digital Library

[18]

Kup, R.M., Upfal, E. and Wigder~a, A., Con- #tructing a Perfect Matching is in Random NC, this conference

[19]

Lev O. Size Bounds and Parallel Algorithms for Networks, Report CST-8-80, Department of Computer Science, University of Edinburgh (1980)

[20]

Tsotsos, J. Representational Axes and Temporal Cooperative Processes, Technical Report RBCV- 84-2, University of Toronto, April 1984

[21]

Vaiiant, L. G. Parallel Computation, Proceedings 7'a IBM Symposium on Malhematical Foundations of Computer Science (1982)

Cited By

Zhou YFang YMa CHou THuang X(2024)Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information NetworksProceedings of the VLDB Endowment10.14778/3681954.368197517:11(2946-2959)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3681975
Dargaville SSmedley-Stevenson RSmith PPain C(2024)Coarsening and parallelism with reduction multigrids for hyperbolic Boltzmann transportThe International Journal of High Performance Computing Applications10.1177/10943420241304759Online publication date: 13-Dec-2024
https://doi.org/10.1177/10943420241304759
Ghaffari MTrygub AAgrawal KPetrank E(2024)Parallel Dynamic Maximal MatchingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659982(427-437)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659982
Show More Cited By

Index Terms

Recommendations

An improved distributed algorithm for maximal independent set
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which ...
Distributed maximal independent set using small messages
SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Maximal Independent Set (MIS) is one of the central problems in distributed graph algorithms. The celebrated works of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86] provide O(log n)-round randomized distributed MIS algorithms, which work with O(log ...
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Special Issue for SPAA 2014

Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Essentially, the challenge is to design (randomized) algorithms in which the number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

December 1985

484 pages

ISBN:0897911512

DOI:10.1145/22145

Chairman:
Robert Sedgewick

Copyright © 1985 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: 01 December 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC85

Sponsor:

SIGACT

STOC85: Annual ACM Conference on Theory of Computing

May 6 - 8, 1985

Rhode Island, Providence, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

190
Total Citations
View Citations
3,729
Total Downloads

Downloads (Last 12 months)355
Downloads (Last 6 weeks)91

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou YFang YMa CHou THuang X(2024)Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information NetworksProceedings of the VLDB Endowment10.14778/3681954.368197517:11(2946-2959)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3681975
Dargaville SSmedley-Stevenson RSmith PPain C(2024)Coarsening and parallelism with reduction multigrids for hyperbolic Boltzmann transportThe International Journal of High Performance Computing Applications10.1177/10943420241304759Online publication date: 13-Dec-2024
https://doi.org/10.1177/10943420241304759
Ghaffari MTrygub AAgrawal KPetrank E(2024)Parallel Dynamic Maximal MatchingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659982(427-437)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659982
Anderson DBlelloch GAgrawal KPetrank E(2024)Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic TreesProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659976(247-258)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659976
Ghaffari MGrunau CMohar BShinkar IO'Donnell R(2024)Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649782(1184-1191)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649782
Assadi SKonrad CNaidu KSundaresan JMohar BShinkar IO'Donnell R(2024)O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent SetProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649763(847-858)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649763
Huang CMak WKim T(2024)CTQr: Control and Timing-Aware Qubit RoutingProceedings of the 29th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC58780.2024.10473795(140-145)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1109/ASP-DAC58780.2024.10473795
Centofanti EScacchi S(2024)A comparison of Algebraic Multigrid Bidomain solvers on hybrid CPU–GPU architecturesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.116875423(116875)Online publication date: Apr-2024
https://doi.org/10.1016/j.cma.2024.116875
Brighen AChouikh AIkhlef HSlimani HRezgui AKheddouci H(2024)Giraph-Based Distributed Algorithms for Coloring Large-Scale GraphsInternational Journal of Parallel Programming10.1007/s10766-024-00781-053:1Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1007/s10766-024-00781-0
Fatemi ZZheleva E(2023)Network experiment designs for inferring causal effects under interferenceFrontiers in Big Data10.3389/fdata.2023.11286496Online publication date: 17-Apr-2023
https://doi.org/10.3389/fdata.2023.1128649
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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