Richard M. Karp
Avi Wigderson
Abstract
A parallel algorithm is presented that accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n)4) time and uses O((n/(log n))3) processors, where n is the number of vertices in G. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.
- 1 COOK, S. A.An overview of computational complexity. Commun. ACM 26, 6 (1983), 400-408. Google Scholar
- 2 COOK, S. A.The classification of problems which have fast parallel algorithms. Tech. Rep. No. 164/83, Dept. of Comput. Sci., Univ. of Toronto, Toronto, Ont., Canada, 1983.Google Scholar
- 3 HALL, M.Combinatorial Theory. Blaisdell, Waltham, Mass., 1967.Google Scholar
- 4 JONES, N. D., LIEN, Y. E., AND LAASER, W. T.New problems complete for nondeterministic log space. Math. Syst. Theory 10 (1976), 1-17.Google Scholar
- 5 LEV, G. Size bounds and parallel algorithms for networks. Rep. CST-8-80, Dept. of Comput. Sci., Univ. of Edinburgh, Edinburgh, Scotland, 1980.Google Scholar
- 6 VALIANT, L. G. Parallel computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. IBM, New York, 1982.Google Scholar
Index Terms
- A fast parallel algorithm for the maximal independent set problem
Recommendations
A fast parallel algorithm for the maximal independent set problem
STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingA parallel algorithm is presented which accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n)4) time and uses O((n/log ...
An improved distributed algorithm for maximal independent set
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithmsThe 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 ...
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Special Issue for SPAA 2014Whether 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 ...
Reviews
Christoph M. Hoffmann
An independent set of a simple graph is a subset of vertices, no two of which are adjacent. The paper describes a P-RAM algorithm to determine a maximal independent set for a given graph. The bounds achieved are O((log n) 4) deterministic time with O( n 3/(log n) 3) processors. There is also a sketch of a probabilistic algorithm requiring O( n 2) processors taking O((log n) 3) expected time. The basic strategy is to select an independent set and repeatedly add to it. The difficulty consists of selecting sufficiently large subsets at each adding stage. By means of combinatorial arguments, it is shown that these sets should be located within subsets of vertices of above average valence. The subsets can be chosen at random, leading to a probabilistic algorithm, or deterministically, the latter requiring a balanced incomplete block design.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments