A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM

被引：442

作者：

ALON, N

BABAI, L

ITAI, A

机构：

[1] MIT,DEPT MATH,CAMBRIDGE,MA 02139

[2] TEL AVIV UNIV,DEPT MATH,IL-69978 TEL AVIV,ISRAEL

[3] UNIV CHICAGO,DEPT COMP SCI,CHICAGO,IL 60637

[4] EOTVOS LORAND UNIV,DEPT ALGEBRA,H-1364 BUDAPEST 5,HUNGARY

[5] TECHNION ISRAEL INST TECHNOL,DEPT COMP SCI,HAIFA,ISRAEL

来源：

关键词：

D O I：

10.1016/0196-6774(86)90019-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：567 / 583

页数：17

共 24 条

[1]

Ajtai M., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P11, DOI 10.1109/SFCS.1985.19

[2]

Alexi W., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P449, DOI 10.1109/SFCS.1984.715947

[3]

ALON N, EUROPEAN J COMBIN

[4]

ANDERSON R, 1985, SET SPLITTING

[5]

Babai L., 1985, EUR J COMBIN, V6, P101

[6]

BERNSTEIN S, 1945, THEORY PROBABILITY

[7]

Chor B., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P396, DOI 10.1109/SFCS.1985.55

[8]

CHOR B, 1985, POWER 2 POINTS BASED

[9]

Cook S. A., 1983, Communications of the ACM, V26, P400, DOI 10.1145/358141.358144

[10] SOME REMARKS ON THE THEORY OF GRAPHS [J].

ERDOS, P .